摘要：The well-quasi-ordering (i.e., a well-founded quasi-ordering such that allantichains are finite) that defines well-structured transition systems (WSTS)is shown not to be the weakest hypothesis that implies decidability of thecoverability problem. We show coverability decidable for monotone transitionsystems that only require the absence of infinite antichains and call wellbehaved transitions systems (WBTS) the new strict superclass of the class ofWSTS that arises. By contrast, we confirm that boundedness and termination areundecidable for WBTS under the usual hypotheses, and show that strongermonotonicity conditions can enforce decidability. Proofs are similar or evenidentical to existing proofs but the surprising message is that a hypothesisimplicitely assumed minimal for twenty years in the theory of WSTS canmeaningfully be relaxed, allowing more orderings to be handled in an abstractway.
关键词：F.3.1;F.1.1;Computer Science - Logic in Computer Science
