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.|
|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)|
|References:||Aldis, J. W.  “A polynomial time algorithm to determine maximal balanced equivalence relations,” Masters thesis, University of Warwick. Davey, B. A. & Priestley, H. A.  Introduction to Lattices and Order, 1st edition (Cambridge University Press, Cambridge). Golubitsky, M., Stewart, I. N. & Nicol, M.  “Some curious phenomena in coupled cell networks,” J. Nonlin. Sci. 14, 207–236. Golubitsky, M., Stewart, I. N. & T¨or¨ok, A.  “Patterns of synchrony in coupled cell networks with multiple arrows,” SIAM J. Appl. Dyn. Syst. 4, 78–100. Golubitsky, M. & Stewart, I. N.  “Nonlinear dynamics of networks: The groupoid formalism,” Bull. Amer. Math. Soc. 43, 305–364. Stewart, I. N., Golubitsky, M. & Pivato, M.  “Symmetry groupoids and patterns of synchrony in coupled cell networks,” SIAM J. Appl. Dyn. Syst. 2, 609–646. Stewart, I. N.  “The lattice of balanced equivalence relations of a coupled cell network,” Math. Proc. Camb. Phil. Soc. 143, 165–183.|
Actions (login required)