An approach to incompletely specified finite state machine minimization / Uma estratégia para a minimização de máquinas de estados finitos parciais

AUTOR(ES)
DATA DE PUBLICAÇÃO

2009

RESUMO

Finite State Machines are largely used on Software Engineering to model systems specifications. In these models, designers may inadvertently include redundant states, i.e., states which exhibit the same input/output behavior. The absence of such states brings benefits to the modeling activities, reducing the complexity and taking less physical resources on implementations. The process of eliminating redundant states is known as minimization, and can be accomplished in polynomial time for completely specified machines. On the other hand, the minimization of partially specified machines, i.e., machines which have undefined behavior for some inputs, can only be done in polynomial time when non-deterministic approaches are applied. It is a known NP-Complete problem. This work presents a deterministic approach to minimize incompletely specified Finite State Machines, using heuristics and optimizations to accomplish the task more efficiently. In order to measure the performance improvements, experiments were done, observing the running time of an implementation of the proposed method, along with running times of implementations of two other known methods. The results revealed a significant performance advantage when using the proposed approach

ASSUNTO(S)

incompletely specified finite state machine fsm minimization minimização máquinas de estados finitos parciais mef parcialmente especificada

ACESSO AO ARTIGO

Documentos Relacionados