On Finite Representations of Infinite-State Behaviours

摘要

We examine the problem of finite-state representability of infinite-state processes w.r.t. certain behavioural equivalences. We show that the clas-sical notion of regularity becomes insufficient in case of all equivalences of van Glabbeek's hierarchy except bisimilarity, and we design and justify a generaliza-tion in the form of strong regularity and finite characterizations. We show that the condition of strong regularity guarantees an existence of finite characterization in case of all equivalences of van Glabbeek's hierarchy, and we also demonstrate that there are behaviours which are regular but not strongly regular w.r.t. all equiv-alences of the mentioned hierarchy except bisimilarity.