  Lexicographic Ranking SuperMartingale (LexRSM) is a probabilistic extension
of Lexicographic Ranking Function (LexRF), which is a widely accepted technique
for verifying program termination. In this paper, we are the first to propose
sound probabilistic extensions of LexRF with a weaker non-negativity condition,
called single-component (SC) non-negativity. It is known that such an
extension, if it exists, will be nontrivial due to the intricacies of the
probabilistic circumstances.
  Toward the goal, we first devise the notion of fixability, which offers a
systematic approach for analyzing the soundness of possibly negative LexRSM.
This notion yields a desired extension of LexRF that is sound for general
stochastic processes. We next propose another extension, called Lazy LexRSM,
toward the application to automated verification; it is sound over
probabilistic programs with linear arithmetics, while its subclass is amenable
to automated synthesis via linear programming. We finally propose a LexRSM
synthesis algorithm for this subclass, and perform experiments.
