Skip to main content

Equivalences within Non-Finite State Systems

J Bradley, N Davies, Equivalences within Non-Finite State Systems. Proceedings of the Fifth IFIP Workshop on Performance Modelling and Evaluation of ATM Networks. ISBN 0 9524027 3 4, pp. 82001–82010. July 1997. PDF, 169 Kbytes.


In this paper, we discuss the issues associated with proving complete equivalences within Non-Finite State Systems. The various forms of equivalence that can exist between two algebraically defined systems can be intractable to demonstrate if the systems have infinite state order. This problem leads us to outline the following approach for enabling us to talk about, albeit weaker, approximations of equivalence for infinite systems: The definition of successive finite approximations to equivalences, allows for the construction of simulation tools, which can provide meaningful analysis for Non-Finite State Systems (NFSS) as well as the more usual Finite State Systems. The introduction of this extra variant form of equivalence leads to a discussion of their strictness in comparison with the traditional strict equivalence definitions. The intention being, to show that it is permissible to talk about successive finite approximations approaching strict equivalence in the limit. And finally we want to make suggestions as to how this methodology might be extended in future work to encompass equivalence between non-finite stochastic models. Such an extension would allow for the development of classes of models which all share performance characteristics which lie within acceptable bounds. A characterisation of such models, would be a powerful modelling tool for optimising performance and reliability in proposed network protocols.

Bibtex entry.

Contact details

Publication Admin