On limit cycles of monotone functions with symmetric connection graph

Aracena, J; Demongeot, J.; Goles, E.

Abstract

We study the length of the limit cycles of discrete monotone functions with symmetric connection graph. We construct a family of monotone functions such that the limit cycles are of maximum possible length, which is exponential in the number of variables. Furthermore, we prove for the class of monotone functions with more than two states and connection graph equal to a caterpillar that the length of the limit cycles is at most two. Finally, we give some exclusion results in arbitrary trees. © 2004 Elsevier B.V. All rights reserved.

Más información

Título según WOS: On limit cycles of monotone functions with symmetric connection graph
Título según SCOPUS: On limit cycles of monotone functions with symmetric connection graph
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 322
Número: 2
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2004
Página de inicio: 237
Página final: 244
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0304397504001616
DOI:

10.1016/j.tcs.2004.03.010

Notas: ISI, SCOPUS