A polynomial time algorithm to determine maximal balanced equivalence relations
Aldis, John W.. (2008) A polynomial time algorithm to determine maximal balanced equivalence relations. International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, Volume 18 (Number 2). pp. 407-427. ISSN 0218-1274Full text not available from this repository.
Official URL: http://www.worldscinet.com/ijbc/18/1802/S021812740...
Following Golubitsky, Stewart, and others, we give definitions of networks and input trees. In order to make our work as general as possible, we work with a somewhat extended notion of multiplicity, and introduce the concept of "bunching" of trees. We then de. ne balanced equivalence relations on networks, and a partial ordering on these relations. Previous work has shown that there is a maximal balanced equivalence relation on networks of certain classes: we provide a different style of proof which gives this result for any network. We de. ne two algorithms to determine this relation in practice on a given finite network-one for use with networks with all multiplicities equal, and a second for the more general case. We then provide illustrative examples of each algorithm in use. We show both of these algorithms to be quartic in the size of the given network.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics
|Divisions:||Faculty of Science > Mathematics|
|Library of Congress Subject Headings (LCSH):||Algorithms, Polynomials, Lattice theory, Equivalence relations (Set theory)|
|Journal or Publication Title:||International Journal of Bifurcation and Chaos in Applied Sciences and Engineering|
|Publisher:||World Scientific Publishing Co. Pte. Ltd.|
|Official Date:||February 2008|
|Number of Pages:||21|
|Page Range:||pp. 407-427|
|Access rights to Published version:||Restricted or Subscription Access|
|Funder:||Engineering and Physical Sciences Research Council (EPSRC)|
Aldis, J. W.  “A polynomial time algorithm to
Actions (login required)
Downloads per month over past year