On finite representations of infinite-state behaviours

We examine the problem of finite-state representability of infinite-state p rocesses with respect to certain behavioral equivalences. We argue that the classical notion of regularity becomes insufficient in many practical situ ations, and we design and justify new notions of strong regularity and fini te characterization. We show that the condition of strong regularity guaran tees the existence of a finite characterization for all equivalences of van Glabbeek's hierarchy, and we also demonstrate that there are behaviours wh ich are regular but not strongly regular with respect to all equivalences o f the mentioned hierarchy except bisimilarity. Finally, we prove that decid ability issues for strong regularity are quite different from the ones for regularity. We show that strong regularity with respect to almost all equiv alences of van Glabbeek's hierarchy is decidable in a large class of infini te-state processes, while regularity with respect to some of those equivale nces is undecidable. (C) 1999 Elsevier Science B.V. All rights reserved.