./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound100.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_unwindbound100.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 30672bd579b7f25ffa685cb80d8a419cb542781c19afe0226ba5d9d3cf26984c --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:00:28,353 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:00:28,399 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:28,403 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:00:28,403 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:00:28,423 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:00:28,424 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:00:28,424 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:00:28,424 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:00:28,424 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:00:28,424 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:00:28,424 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:00:28,424 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:00:28,424 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:00:28,424 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:00:28,425 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:00:28,425 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:00:28,425 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:28,426 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:00:28,426 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:00:28,426 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 -> 30672bd579b7f25ffa685cb80d8a419cb542781c19afe0226ba5d9d3cf26984c [2025-03-08 05:00:28,653 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:00:28,662 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:00:28,666 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:00:28,667 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:00:28,668 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:00:28,670 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound100.c [2025-03-08 05:00:29,859 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f76a986f5/83e2288b4b3c4c2e967088b172993a43/FLAGed3c96e46 [2025-03-08 05:00:30,077 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:00:30,082 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound100.c [2025-03-08 05:00:30,091 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f76a986f5/83e2288b4b3c4c2e967088b172993a43/FLAGed3c96e46 [2025-03-08 05:00:30,116 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f76a986f5/83e2288b4b3c4c2e967088b172993a43 [2025-03-08 05:00:30,119 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:00:30,122 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:00:30,123 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:30,124 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:00:30,127 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:00:30,128 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:30" (1/1) ... [2025-03-08 05:00:30,129 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6a5d3808 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:30, skipping insertion in model container [2025-03-08 05:00:30,130 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:30" (1/1) ... [2025-03-08 05:00:30,145 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:00:30,267 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_unwindbound100.c[490,503] [2025-03-08 05:00:30,292 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:30,300 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:00:30,307 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_unwindbound100.c[490,503] [2025-03-08 05:00:30,319 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:30,329 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:00:30,330 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:30 WrapperNode [2025-03-08 05:00:30,330 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:30,332 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:30,332 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:00:30,332 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:00:30,338 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:30" (1/1) ... [2025-03-08 05:00:30,344 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:30" (1/1) ... [2025-03-08 05:00:30,359 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-08 05:00:30,360 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:30,361 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:00:30,361 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:00:30,361 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:00:30,367 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:30" (1/1) ... [2025-03-08 05:00:30,367 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:30" (1/1) ... [2025-03-08 05:00:30,368 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:30" (1/1) ... [2025-03-08 05:00:30,381 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:30,382 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:30" (1/1) ... [2025-03-08 05:00:30,382 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:30" (1/1) ... [2025-03-08 05:00:30,385 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:30" (1/1) ... [2025-03-08 05:00:30,388 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:30" (1/1) ... [2025-03-08 05:00:30,394 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:30" (1/1) ... [2025-03-08 05:00:30,395 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:30" (1/1) ... [2025-03-08 05:00:30,396 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:00:30,397 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:00:30,397 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:00:30,397 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:00:30,398 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:30" (1/1) ... [2025-03-08 05:00:30,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:30,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:30,427 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:30,430 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:30,448 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:00:30,448 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 05:00:30,448 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 05:00:30,448 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:00:30,449 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:00:30,449 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:00:30,449 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:00:30,449 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:00:30,492 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:00:30,494 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:00:30,646 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-08 05:00:30,646 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:00:30,652 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:00:30,653 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:00:30,653 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:30 BoogieIcfgContainer [2025-03-08 05:00:30,653 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:00:30,655 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:00:30,655 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:00:30,659 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:00:30,660 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:00:30" (1/3) ... [2025-03-08 05:00:30,661 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77fb6e92 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:30, skipping insertion in model container [2025-03-08 05:00:30,661 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:30" (2/3) ... [2025-03-08 05:00:30,661 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77fb6e92 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:30, skipping insertion in model container [2025-03-08 05:00:30,661 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:30" (3/3) ... [2025-03-08 05:00:30,663 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound100.c [2025-03-08 05:00:30,674 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:00:30,676 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound100.c that has 3 procedures, 34 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:00:30,713 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:00:30,725 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;@5fbbc8e4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:00:30,725 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:00:30,729 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:30,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-08 05:00:30,736 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:30,736 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:30,737 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:30,740 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:30,741 INFO L85 PathProgramCache]: Analyzing trace with hash 100709880, now seen corresponding path program 1 times [2025-03-08 05:00:30,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:30,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [959267712] [2025-03-08 05:00:30,748 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:30,748 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:30,792 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:30,806 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:30,807 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:30,807 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:30,857 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:30,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:30,858 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [959267712] [2025-03-08 05:00:30,858 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [959267712] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:30,858 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1173444828] [2025-03-08 05:00:30,858 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:30,858 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:30,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:30,862 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:30,863 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:30,899 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:30,921 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:30,921 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:30,921 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:30,923 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 05:00:30,925 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:30,936 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:30,936 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:30,936 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1173444828] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:30,936 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:30,937 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 05:00:30,939 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1986427112] [2025-03-08 05:00:30,939 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:30,942 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:00:30,943 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:30,958 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:00:30,958 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:00:30,960 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:30,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:30,982 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2025-03-08 05:00:30,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:00:30,985 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:30,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:30,990 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:30,990 INFO L226 Difference]: Without dead ends: 30 [2025-03-08 05:00:30,993 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:30,997 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:30,998 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:31,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-08 05:00:31,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2025-03-08 05:00:31,026 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:31,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2025-03-08 05:00:31,033 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2025-03-08 05:00:31,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:31,034 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2025-03-08 05:00:31,035 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:31,035 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2025-03-08 05:00:31,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-08 05:00:31,036 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:31,036 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:31,043 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:31,241 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:31,241 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:31,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:31,242 INFO L85 PathProgramCache]: Analyzing trace with hash -1726789354, now seen corresponding path program 1 times [2025-03-08 05:00:31,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:31,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1909019783] [2025-03-08 05:00:31,242 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,242 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:31,256 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-08 05:00:31,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-08 05:00:31,274 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,274 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,417 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:31,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:31,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1909019783] [2025-03-08 05:00:31,418 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1909019783] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:31,418 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:31,418 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 05:00:31,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2053005787] [2025-03-08 05:00:31,418 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:31,419 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 05:00:31,419 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:31,419 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 05:00:31,420 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:00:31,420 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:31,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:31,450 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-08 05:00:31,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 05:00:31,450 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:31,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:31,451 INFO L225 Difference]: With dead ends: 40 [2025-03-08 05:00:31,451 INFO L226 Difference]: Without dead ends: 32 [2025-03-08 05:00:31,451 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:31,452 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:31,452 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:31,452 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-08 05:00:31,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-08 05:00:31,456 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:31,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2025-03-08 05:00:31,457 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2025-03-08 05:00:31,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:31,459 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2025-03-08 05:00:31,459 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:31,459 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2025-03-08 05:00:31,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-08 05:00:31,460 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:31,461 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:31,461 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 05:00:31,461 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:31,461 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:31,461 INFO L85 PathProgramCache]: Analyzing trace with hash -2044305484, now seen corresponding path program 1 times [2025-03-08 05:00:31,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:31,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1019626130] [2025-03-08 05:00:31,462 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:31,473 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:31,495 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:31,495 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,495 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,676 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:31,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:31,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1019626130] [2025-03-08 05:00:31,677 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1019626130] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:31,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [980199910] [2025-03-08 05:00:31,677 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:31,677 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:31,682 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:31,683 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:31,710 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:31,737 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:31,737 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,737 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,739 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:31,741 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:31,892 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:31,894 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:31,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [980199910] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:31,895 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:31,895 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-08 05:00:31,895 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1777928715] [2025-03-08 05:00:31,895 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:31,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:31,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:31,896 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:31,896 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:31,896 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:32,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:32,005 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-08 05:00:32,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:32,005 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:32,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:32,008 INFO L225 Difference]: With dead ends: 49 [2025-03-08 05:00:32,008 INFO L226 Difference]: Without dead ends: 47 [2025-03-08 05:00:32,009 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:32,009 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:32,009 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:32,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-08 05:00:32,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2025-03-08 05:00:32,021 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:32,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2025-03-08 05:00:32,025 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2025-03-08 05:00:32,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:32,026 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2025-03-08 05:00:32,026 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:32,026 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2025-03-08 05:00:32,027 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 05:00:32,027 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:32,027 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:32,034 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:32,229 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:32,229 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:32,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:32,230 INFO L85 PathProgramCache]: Analyzing trace with hash -886820372, now seen corresponding path program 1 times [2025-03-08 05:00:32,230 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:32,230 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504658954] [2025-03-08 05:00:32,230 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:32,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:32,235 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:32,251 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:32,251 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:32,251 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:32,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1063610417] [2025-03-08 05:00:32,253 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:32,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:32,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:32,255 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:32,258 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:32,284 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:32,303 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:32,304 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:32,304 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:32,305 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:32,306 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:32,346 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:32,346 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:32,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:32,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504658954] [2025-03-08 05:00:32,349 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:32,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1063610417] [2025-03-08 05:00:32,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1063610417] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:32,350 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:32,350 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:32,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1257728927] [2025-03-08 05:00:32,350 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:32,350 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:32,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:32,351 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:32,351 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:32,351 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:32,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:32,405 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2025-03-08 05:00:32,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:32,406 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:32,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:32,408 INFO L225 Difference]: With dead ends: 66 [2025-03-08 05:00:32,409 INFO L226 Difference]: Without dead ends: 64 [2025-03-08 05:00:32,409 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:32,410 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:32,410 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:32,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-03-08 05:00:32,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2025-03-08 05:00:32,421 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:32,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2025-03-08 05:00:32,422 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2025-03-08 05:00:32,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:32,422 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2025-03-08 05:00:32,422 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:32,422 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2025-03-08 05:00:32,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:32,423 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:32,423 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:32,429 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:32,623 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:32,624 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:32,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:32,624 INFO L85 PathProgramCache]: Analyzing trace with hash -276176331, now seen corresponding path program 1 times [2025-03-08 05:00:32,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:32,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750004223] [2025-03-08 05:00:32,624 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:32,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:32,630 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:32,642 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:32,642 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:32,642 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:32,741 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:32,741 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:32,742 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750004223] [2025-03-08 05:00:32,742 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [750004223] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:32,742 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2006918158] [2025-03-08 05:00:32,742 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:32,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:32,743 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:32,746 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:32,747 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:32,775 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:32,789 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:32,789 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:32,789 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:32,790 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:32,791 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:32,902 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:32,903 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:32,903 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2006918158] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:32,903 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:32,903 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-08 05:00:32,903 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2001825620] [2025-03-08 05:00:32,903 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:32,904 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:32,904 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:32,904 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:32,904 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:32,904 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:32,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:32,964 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2025-03-08 05:00:32,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:32,964 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:32,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:32,966 INFO L225 Difference]: With dead ends: 63 [2025-03-08 05:00:32,966 INFO L226 Difference]: Without dead ends: 59 [2025-03-08 05:00:32,968 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:32,968 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:32,968 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:32,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-08 05:00:32,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2025-03-08 05:00:32,976 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:32,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2025-03-08 05:00:32,978 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2025-03-08 05:00:32,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:32,979 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2025-03-08 05:00:32,979 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:32,979 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2025-03-08 05:00:32,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:32,980 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:32,980 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:32,986 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:33,180 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:33,181 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:33,181 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:33,181 INFO L85 PathProgramCache]: Analyzing trace with hash -247836027, now seen corresponding path program 1 times [2025-03-08 05:00:33,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:33,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [260401168] [2025-03-08 05:00:33,181 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:33,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:33,185 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:33,194 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:33,194 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:33,194 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:33,254 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:33,255 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:33,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [260401168] [2025-03-08 05:00:33,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [260401168] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:33,255 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:33,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:33,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1616200330] [2025-03-08 05:00:33,255 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:33,256 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:33,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:33,257 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:33,258 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:33,258 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:33,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:33,289 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2025-03-08 05:00:33,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:33,290 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:33,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:33,291 INFO L225 Difference]: With dead ends: 84 [2025-03-08 05:00:33,291 INFO L226 Difference]: Without dead ends: 58 [2025-03-08 05:00:33,291 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:33,292 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:33,292 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:33,293 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-08 05:00:33,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-08 05:00:33,307 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:33,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2025-03-08 05:00:33,310 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2025-03-08 05:00:33,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:33,310 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-08 05:00:33,310 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:33,311 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2025-03-08 05:00:33,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-08 05:00:33,311 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:33,312 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:33,312 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-08 05:00:33,312 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:33,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:33,312 INFO L85 PathProgramCache]: Analyzing trace with hash -1535941731, now seen corresponding path program 1 times [2025-03-08 05:00:33,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:33,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635764938] [2025-03-08 05:00:33,313 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:33,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:33,322 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:33,337 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:33,337 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:33,338 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:33,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1217961835] [2025-03-08 05:00:33,338 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:33,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:33,339 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:33,342 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:33,344 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:33,374 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:33,390 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:33,391 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:33,391 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:33,391 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:33,395 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:33,543 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:33,543 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:33,543 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:33,543 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635764938] [2025-03-08 05:00:33,543 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:33,543 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1217961835] [2025-03-08 05:00:33,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1217961835] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:33,544 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:33,544 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:33,544 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [867556776] [2025-03-08 05:00:33,544 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:33,544 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:33,544 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:33,544 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:33,545 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:33,545 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:33,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:33,594 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2025-03-08 05:00:33,595 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:33,595 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:33,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:33,596 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:33,596 INFO L226 Difference]: Without dead ends: 63 [2025-03-08 05:00:33,596 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:33,596 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:33,597 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:33,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-08 05:00:33,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-08 05:00:33,612 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:33,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2025-03-08 05:00:33,612 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2025-03-08 05:00:33,613 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:33,613 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2025-03-08 05:00:33,613 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:33,613 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2025-03-08 05:00:33,614 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 05:00:33,614 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:33,614 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:33,621 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-08 05:00:33,814 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:33,814 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:33,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:33,815 INFO L85 PathProgramCache]: Analyzing trace with hash 101798249, now seen corresponding path program 1 times [2025-03-08 05:00:33,815 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:33,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [578987032] [2025-03-08 05:00:33,815 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:33,815 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:33,820 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:33,829 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:33,829 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:33,829 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:33,830 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [495703902] [2025-03-08 05:00:33,830 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:33,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:33,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:33,833 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:33,834 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:33,858 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:33,880 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:33,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:33,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:33,882 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:33,884 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:33,958 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:33,958 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:34,072 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:34,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:34,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [578987032] [2025-03-08 05:00:34,073 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:34,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [495703902] [2025-03-08 05:00:34,073 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [495703902] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:34,073 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:34,073 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-08 05:00:34,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [26616073] [2025-03-08 05:00:34,074 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:34,074 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:34,074 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:34,074 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:34,075 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:34,076 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:34,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:34,166 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2025-03-08 05:00:34,166 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:34,166 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:34,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:34,167 INFO L225 Difference]: With dead ends: 92 [2025-03-08 05:00:34,167 INFO L226 Difference]: Without dead ends: 90 [2025-03-08 05:00:34,168 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:34,168 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 9 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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:34,168 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:34,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-08 05:00:34,182 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 58. [2025-03-08 05:00:34,184 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:34,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2025-03-08 05:00:34,186 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2025-03-08 05:00:34,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:34,187 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2025-03-08 05:00:34,187 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:34,187 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2025-03-08 05:00:34,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-08 05:00:34,188 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:34,188 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:34,195 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:34,388 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:34,389 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:34,389 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:34,389 INFO L85 PathProgramCache]: Analyzing trace with hash -1244697335, now seen corresponding path program 1 times [2025-03-08 05:00:34,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:34,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1664854115] [2025-03-08 05:00:34,389 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:34,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:34,396 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:34,405 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:34,405 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:34,405 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:34,465 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:34,466 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:34,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1664854115] [2025-03-08 05:00:34,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1664854115] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:34,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [436908556] [2025-03-08 05:00:34,466 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:34,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:34,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:34,468 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:34,470 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:34,494 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:34,510 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:34,510 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:34,510 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:34,511 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:34,514 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:34,569 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:34,570 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:34,649 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:34,649 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [436908556] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:34,649 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:34,649 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-08 05:00:34,649 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1010689822] [2025-03-08 05:00:34,650 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:34,650 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:00:34,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:34,650 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:00:34,651 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:34,651 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:34,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:34,818 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2025-03-08 05:00:34,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:00:34,818 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 56 [2025-03-08 05:00:34,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:34,821 INFO L225 Difference]: With dead ends: 211 [2025-03-08 05:00:34,821 INFO L226 Difference]: Without dead ends: 203 [2025-03-08 05:00:34,822 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:34,823 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 81 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:34,823 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 194 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:34,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2025-03-08 05:00:34,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2025-03-08 05:00:34,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2025-03-08 05:00:34,862 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2025-03-08 05:00:34,862 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2025-03-08 05:00:34,863 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:34,863 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2025-03-08 05:00:34,863 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:34,864 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2025-03-08 05:00:34,864 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-08 05:00:34,864 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:34,864 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:34,871 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:35,069 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:35,085 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:35,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:35,086 INFO L85 PathProgramCache]: Analyzing trace with hash 15645217, now seen corresponding path program 1 times [2025-03-08 05:00:35,086 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:35,086 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313010492] [2025-03-08 05:00:35,086 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:35,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:35,094 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:35,105 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:35,105 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:35,105 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:35,213 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:35,214 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:35,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1313010492] [2025-03-08 05:00:35,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1313010492] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:35,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [839689503] [2025-03-08 05:00:35,214 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:35,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:35,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:35,216 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:35,223 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:35,247 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:35,266 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:35,266 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:35,266 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:35,267 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:35,269 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:35,305 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:35,306 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:35,404 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:35,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [839689503] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:35,404 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:35,404 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-08 05:00:35,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1964300866] [2025-03-08 05:00:35,405 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:35,405 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:00:35,405 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:35,406 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:00:35,406 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:35,406 INFO L87 Difference]: Start difference. First operand 195 states and 233 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:35,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:35,583 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2025-03-08 05:00:35,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:00:35,584 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:35,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:35,586 INFO L225 Difference]: With dead ends: 279 [2025-03-08 05:00:35,586 INFO L226 Difference]: Without dead ends: 259 [2025-03-08 05:00:35,587 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:35,587 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:35,587 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 249 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:35,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2025-03-08 05:00:35,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2025-03-08 05:00:35,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-08 05:00:35,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2025-03-08 05:00:35,635 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2025-03-08 05:00:35,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:35,636 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2025-03-08 05:00:35,636 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:35,636 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2025-03-08 05:00:35,637 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-08 05:00:35,637 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:35,637 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:35,645 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:35,839 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:35,839 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:35,840 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:35,840 INFO L85 PathProgramCache]: Analyzing trace with hash -351822558, now seen corresponding path program 1 times [2025-03-08 05:00:35,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:35,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1312555831] [2025-03-08 05:00:35,841 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:35,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:35,847 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:35,854 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:35,855 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:35,855 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:35,919 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:35,919 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:35,919 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1312555831] [2025-03-08 05:00:35,919 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1312555831] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:35,919 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [700308180] [2025-03-08 05:00:35,920 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:35,920 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:35,920 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:35,921 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:35,923 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:35,952 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:35,968 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:35,968 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:35,968 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:35,969 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:35,972 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:36,029 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:36,030 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:36,103 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:36,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [700308180] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:36,104 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:36,104 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-08 05:00:36,104 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [341223937] [2025-03-08 05:00:36,104 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:36,104 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:00:36,104 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:36,105 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:00:36,105 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:36,105 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:36,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:36,253 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2025-03-08 05:00:36,254 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:00:36,254 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 59 [2025-03-08 05:00:36,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:36,256 INFO L225 Difference]: With dead ends: 344 [2025-03-08 05:00:36,256 INFO L226 Difference]: Without dead ends: 248 [2025-03-08 05:00:36,257 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:36,257 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 68 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:36,257 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 179 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:36,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2025-03-08 05:00:36,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2025-03-08 05:00:36,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-08 05:00:36,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2025-03-08 05:00:36,291 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2025-03-08 05:00:36,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:36,292 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2025-03-08 05:00:36,292 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:36,292 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2025-03-08 05:00:36,292 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-08 05:00:36,293 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:36,293 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:36,299 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-08 05:00:36,493 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:36,494 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:36,494 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:36,494 INFO L85 PathProgramCache]: Analyzing trace with hash -1287548176, now seen corresponding path program 1 times [2025-03-08 05:00:36,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:36,494 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1212517526] [2025-03-08 05:00:36,494 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:36,495 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:36,501 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:36,517 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:36,517 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:36,517 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:36,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [650316788] [2025-03-08 05:00:36,518 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:36,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:36,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:36,521 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:36,522 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:36,553 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:36,573 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:36,573 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:36,573 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:36,577 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-08 05:00:36,579 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:36,699 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:36,699 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:36,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:36,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1212517526] [2025-03-08 05:00:36,730 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:36,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [650316788] [2025-03-08 05:00:36,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [650316788] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:36,730 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:36,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-08 05:00:36,731 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [559667603] [2025-03-08 05:00:36,731 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:36,731 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:36,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:36,731 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:36,731 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:36,732 INFO L87 Difference]: Start difference. First operand 244 states and 302 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:36,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:36,819 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2025-03-08 05:00:36,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:36,820 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:36,820 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:36,821 INFO L225 Difference]: With dead ends: 283 [2025-03-08 05:00:36,821 INFO L226 Difference]: Without dead ends: 278 [2025-03-08 05:00:36,822 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:36,822 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:36,823 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:36,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2025-03-08 05:00:36,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2025-03-08 05:00:36,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 183 states have (on average 1.185792349726776) internal successors, (217), 187 states have internal predecessors, (217), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:36,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2025-03-08 05:00:36,850 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2025-03-08 05:00:36,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:36,850 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2025-03-08 05:00:36,850 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:36,850 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2025-03-08 05:00:36,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-08 05:00:36,851 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:36,851 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:36,857 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:37,055 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:37,055 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:37,055 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:37,055 INFO L85 PathProgramCache]: Analyzing trace with hash 691051449, now seen corresponding path program 2 times [2025-03-08 05:00:37,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:37,056 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1262260733] [2025-03-08 05:00:37,056 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:37,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:37,062 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:37,072 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:37,072 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:37,072 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:37,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [96440956] [2025-03-08 05:00:37,073 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:37,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:37,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:37,075 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:37,076 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:37,105 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:37,124 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:37,124 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:37,124 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:37,126 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-08 05:00:37,127 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:37,282 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:37,282 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:37,358 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:37,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1262260733] [2025-03-08 05:00:37,358 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:37,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [96440956] [2025-03-08 05:00:37,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [96440956] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:37,358 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:37,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-08 05:00:37,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [746261165] [2025-03-08 05:00:37,358 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:37,358 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:37,358 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:37,359 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:37,359 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:37,359 INFO L87 Difference]: Start difference. First operand 276 states and 343 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:37,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:37,482 INFO L93 Difference]: Finished difference Result 291 states and 357 transitions. [2025-03-08 05:00:37,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:37,483 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:37,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:37,485 INFO L225 Difference]: With dead ends: 291 [2025-03-08 05:00:37,485 INFO L226 Difference]: Without dead ends: 289 [2025-03-08 05:00:37,485 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:37,485 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:37,485 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:37,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2025-03-08 05:00:37,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 288. [2025-03-08 05:00:37,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 288 states, 192 states have (on average 1.1770833333333333) internal successors, (226), 196 states have internal predecessors, (226), 65 states have call successors, (65), 30 states have call predecessors, (65), 30 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:37,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 352 transitions. [2025-03-08 05:00:37,508 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 352 transitions. Word has length 69 [2025-03-08 05:00:37,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:37,508 INFO L471 AbstractCegarLoop]: Abstraction has 288 states and 352 transitions. [2025-03-08 05:00:37,509 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:37,509 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 352 transitions. [2025-03-08 05:00:37,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-08 05:00:37,509 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:37,509 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:37,516 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-08 05:00:37,710 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:37,710 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:37,711 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:37,711 INFO L85 PathProgramCache]: Analyzing trace with hash 239571152, now seen corresponding path program 3 times [2025-03-08 05:00:37,711 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:37,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325292537] [2025-03-08 05:00:37,711 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:37,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:37,716 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:37,729 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:37,731 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 05:00:37,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:37,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1778814593] [2025-03-08 05:00:37,731 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:37,731 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:37,732 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:37,734 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:37,736 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:37,762 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:37,777 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:37,777 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 05:00:37,777 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:37,779 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-08 05:00:37,782 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:38,117 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:38,117 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:38,355 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:38,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325292537] [2025-03-08 05:00:38,355 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:38,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1778814593] [2025-03-08 05:00:38,355 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1778814593] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:38,355 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:38,355 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-08 05:00:38,355 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1266151322] [2025-03-08 05:00:38,355 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:38,355 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 05:00:38,355 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:38,356 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 05:00:38,356 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:00:38,356 INFO L87 Difference]: Start difference. First operand 288 states and 352 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:38,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:38,567 INFO L93 Difference]: Finished difference Result 303 states and 366 transitions. [2025-03-08 05:00:38,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:00:38,568 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:38,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:38,569 INFO L225 Difference]: With dead ends: 303 [2025-03-08 05:00:38,569 INFO L226 Difference]: Without dead ends: 299 [2025-03-08 05:00:38,569 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:38,570 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 26 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:38,570 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 281 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:00:38,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2025-03-08 05:00:38,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 298. [2025-03-08 05:00:38,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 298 states, 200 states have (on average 1.165) internal successors, (233), 203 states have internal predecessors, (233), 65 states have call successors, (65), 33 states have call predecessors, (65), 32 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:38,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 298 states to 298 states and 359 transitions. [2025-03-08 05:00:38,592 INFO L78 Accepts]: Start accepts. Automaton has 298 states and 359 transitions. Word has length 74 [2025-03-08 05:00:38,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:38,592 INFO L471 AbstractCegarLoop]: Abstraction has 298 states and 359 transitions. [2025-03-08 05:00:38,592 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:38,592 INFO L276 IsEmpty]: Start isEmpty. Operand 298 states and 359 transitions. [2025-03-08 05:00:38,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-08 05:00:38,593 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:38,593 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:38,599 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-03-08 05:00:38,793 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:38,794 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:38,794 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:38,794 INFO L85 PathProgramCache]: Analyzing trace with hash 852496708, now seen corresponding path program 1 times [2025-03-08 05:00:38,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:38,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1205010297] [2025-03-08 05:00:38,794 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:38,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:38,798 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:38,810 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:38,810 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:38,810 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:38,811 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [307228652] [2025-03-08 05:00:38,811 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:38,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:38,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:38,813 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:38,815 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:38,841 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:38,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:38,861 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:38,861 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:38,867 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-08 05:00:38,868 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:39,326 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:39,326 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:39,664 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:39,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:39,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1205010297] [2025-03-08 05:00:39,665 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:39,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [307228652] [2025-03-08 05:00:39,665 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [307228652] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:39,665 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:39,665 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-08 05:00:39,665 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1833621661] [2025-03-08 05:00:39,665 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:39,666 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-08 05:00:39,666 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:39,666 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-08 05:00:39,666 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-08 05:00:39,667 INFO L87 Difference]: Start difference. First operand 298 states and 359 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:41,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:41,229 INFO L93 Difference]: Finished difference Result 435 states and 581 transitions. [2025-03-08 05:00:41,229 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 05:00:41,229 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:41,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:41,233 INFO L225 Difference]: With dead ends: 435 [2025-03-08 05:00:41,233 INFO L226 Difference]: Without dead ends: 428 [2025-03-08 05:00:41,234 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-08 05:00:41,235 INFO L435 NwaCegarLoop]: 61 mSDtfsCounter, 134 mSDsluCounter, 700 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 761 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:41,235 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 761 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-08 05:00:41,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 428 states. [2025-03-08 05:00:41,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 428 to 391. [2025-03-08 05:00:41,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 256 states have (on average 1.23046875) internal successors, (315), 259 states have internal predecessors, (315), 100 states have call successors, (100), 34 states have call predecessors, (100), 34 states have return successors, (98), 97 states have call predecessors, (98), 98 states have call successors, (98) [2025-03-08 05:00:41,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 513 transitions. [2025-03-08 05:00:41,294 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 513 transitions. Word has length 80 [2025-03-08 05:00:41,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:41,294 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 513 transitions. [2025-03-08 05:00:41,294 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:41,295 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 513 transitions. [2025-03-08 05:00:41,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-08 05:00:41,295 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:41,295 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:41,303 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-08 05:00:41,497 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:41,497 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:41,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:41,498 INFO L85 PathProgramCache]: Analyzing trace with hash 2042434077, now seen corresponding path program 4 times [2025-03-08 05:00:41,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:41,498 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1553112396] [2025-03-08 05:00:41,498 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:00:41,498 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:41,509 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 91 statements into 2 equivalence classes. [2025-03-08 05:00:41,518 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 81 of 91 statements. [2025-03-08 05:00:41,519 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-08 05:00:41,519 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:41,592 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-03-08 05:00:41,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:41,592 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1553112396] [2025-03-08 05:00:41,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1553112396] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:41,592 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:41,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:41,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [999332957] [2025-03-08 05:00:41,592 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:41,592 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:41,592 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:41,593 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:41,593 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:41,593 INFO L87 Difference]: Start difference. First operand 391 states and 513 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-08 05:00:41,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:41,736 INFO L93 Difference]: Finished difference Result 587 states and 831 transitions. [2025-03-08 05:00:41,736 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:41,737 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 91 [2025-03-08 05:00:41,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:41,739 INFO L225 Difference]: With dead ends: 587 [2025-03-08 05:00:41,739 INFO L226 Difference]: Without dead ends: 462 [2025-03-08 05:00:41,740 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:41,740 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 12 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:41,740 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 186 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:41,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 462 states. [2025-03-08 05:00:41,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 462 to 410. [2025-03-08 05:00:41,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 267 states have (on average 1.2397003745318351) internal successors, (331), 270 states have internal predecessors, (331), 108 states have call successors, (108), 34 states have call predecessors, (108), 34 states have return successors, (106), 105 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-08 05:00:41,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 545 transitions. [2025-03-08 05:00:41,797 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 545 transitions. Word has length 91 [2025-03-08 05:00:41,797 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:41,797 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 545 transitions. [2025-03-08 05:00:41,797 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-08 05:00:41,797 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 545 transitions. [2025-03-08 05:00:41,798 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-08 05:00:41,798 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:41,798 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:41,798 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-08 05:00:41,798 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:41,798 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:41,798 INFO L85 PathProgramCache]: Analyzing trace with hash 777061389, now seen corresponding path program 1 times [2025-03-08 05:00:41,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:41,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675279216] [2025-03-08 05:00:41,799 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:41,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:41,803 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:41,816 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:41,816 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:41,816 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:41,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1041453156] [2025-03-08 05:00:41,817 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:41,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:41,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:41,820 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:41,822 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:41,849 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:41,873 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:41,874 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:41,874 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:41,875 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-08 05:00:41,877 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:42,665 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:42,665 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:01:08,506 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:08,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:01:08,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [675279216] [2025-03-08 05:01:08,506 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:01:08,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1041453156] [2025-03-08 05:01:08,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1041453156] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:01:08,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:01:08,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-08 05:01:08,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [436013006] [2025-03-08 05:01:08,506 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:01:08,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-08 05:01:08,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:01:08,507 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-08 05:01:08,507 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=539, Unknown=0, NotChecked=0, Total=650 [2025-03-08 05:01:08,507 INFO L87 Difference]: Start difference. First operand 410 states and 545 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:19,649 WARN L286 SmtUtils]: Spent 10.08s 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:01:26,925 WARN L286 SmtUtils]: Spent 7.10s 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:01:31,472 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:01:35,540 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:01:45,397 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:01:50,410 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:02:07,257 WARN L286 SmtUtils]: Spent 12.62s on a formula simplification that was a NOOP. DAG size: 70 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:02:12,145 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 []