JUCS - Journal of Universal Computer Science 14(15): 2532-2548, doi: 10.3217/jucs-014-15-2532
Quantum-Inspired Evolutionary State Assignment for Synchronous Finite State Machines
expand article infoMarcos Paulo Mello Araujo‡, Nadia Nedjah‡, Luiza de Macedo Mourelle‡
‡ State University of Rio de Janeiro, Rio de Janeiro, Brazil

Corresponding author: Marcos Paulo Mello Araujo ( marcos@eng.uerj.br )

© Marcos Paulo Mello Araujo, Nadia Nedjah, Luiza Mourelle.
This article is freely available under the J.UCS Open Content License.
Citation: Araujo MPM, Nedjah N, Mourelle LM (2008) Quantum-Inspired Evolutionary State Assignment for Synchronous Finite State Machines. JUCS - Journal of Universal Computer Science 14(15): 2532-2548. https://doi.org/10.3217/jucs-014-15-2532
Open Access
Abstract
Synchronous finite state machines are very important for digital sequential designs. Among other important aspects, they represent a powerful way for synchronizing hardware components so that these components may cooperate adequately in the fulfillment of the main objective of the hardware design. In this paper, we propose an evolutionary methodology to solve one of the problems related to the design of finite state machines. We optimally solve the state assignment NP -complete problem using a quantum inspired evolutionary algorithm. This is motivated by the fact that with an optimal state assignment one can physically implement the state machine using a minimal hardware area and response time.
Keywords
Quantum computation, finite state machine, state assignment problem