OpenstarTs >
EUT-Periodici >
Rendiconti dell’Istituto di matematica dell’Università di Trieste: an International Journal of Mathematics >
Rendiconti dell‘ Istituto di matematica dell‘ Università di Trieste: an International Journal of Mathematics vol.42 (2010) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10077/3892

Title: Bisimilarity, Hypersets, and Stable Partitioning: a Survey
Authors: Omodeo, Eugenio G.
Keywords: Partition Refinement
Bisimulation
Bisimilarity
Stability
Non-Well-Founded Sets
Issue Date: 2010
Publisher: EUT Edizioni Università di Trieste
Citation: Eugenio G. Omodeo, "Bisimilarity, Hypersets, and Stable Partitioning: a Survey", in: Rendiconti dell’Istituto di Matematica dell’Università di Trieste. An International Journal of Mathematics, 42 (2010), pp. 211-234.
Series/Report no.: Rendiconti dell’Istituto di Matematica dell’Università di Trieste. An International Journal of Mathematics;42 (2010)
Abstract: Since Hopcroft proposed his celebrated $n \log n$ algorithm for minimizing states in a finite automaton, the race for efficient partition refinement methods has inspired much research in algorithmics. In parallel, the notion of bisimulation has gained ground in theoretical investigations not less than in applications, till it even pervaded the axioms of a variant Zermelo-Fraenkel set theory. As is well-known, the coarsest stable partitioning problem and the determination of bisimilarity (i.e., the largest partition stable relative to finitely many dyadic relations) are two faces of the same coin. While there is a tendency to refer these topics to varying frameworks, we will contend that the set-theoretic view not only offers a clear conceptual background (provided stability is referred to a non-well-founded membership), but is leading to new insights on the algorithmic complexity issues.
URI: http://hdl.handle.net/10077/3892
ISSN: 0049-4704
MS Classification 2000: 68Q25
05C85
03E75
03E70
03E30
Appears in Collections:Rendiconti dell‘ Istituto di matematica dell‘ Università di Trieste: an International Journal of Mathematics vol.42 (2010)

Files in This Item:

File Description SizeFormat
Omodeo RendMat42.pdf368.84 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.