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)
Alex Donizeti Betez Alberto
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
Documentos Relacionados
- MINIMIZATION OF INCOMPLETELY SPECIFIED SEQUENTIAL MACHINE FOR HEURISTIC PROCESSES
- Minimização de conjuntos de casos de teste para máquinas de estados finitos
- Geração automática de casos de testes para máquinas de estados finitos
- Test case generation for space area systems using test criteria for finite state machines
- Uma aplicação em esquematização de máquinas