Symbolic two-dimensional minimization of strongly unspecified finite statemachines

Citation
Ma. Perkowski et al., Symbolic two-dimensional minimization of strongly unspecified finite statemachines, J SYST ARCH, 47(1), 2001, pp. 15-28
Citations number
31
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF SYSTEMS ARCHITECTURE
ISSN journal
1383-7621 → ACNP
Volume
47
Issue
1
Year of publication
2001
Pages
15 - 28
Database
ISI
SICI code
1383-7621(200101)47:1<15:STMOSU>2.0.ZU;2-#
Abstract
A generalization of the classical state minimization problem for finite sta te machine (FSM) is proposed and discussed. In contrast to classical state minimization algorithms that minimize in one dimension (states), our algori thm minimizes the FSM in two dimensions: the numbers of both input symbols and internal state symbols are minimized in an iterative sequence of input minimization and state minimization procedures. This approach leads to an i nput decomposition of the FSM. A modified formulation of the state minimiza tion problem is also introduced, and an efficient branch-and-bound program, FMINI, is presented. FMINI produces an exact minimum result for each compo nent minimization process and a globally quasi-minimum solution to the enti re two-dimensional (2D) FSM minimization problem. For some benchmarks, espe cially those with a high percentage of don't cares, as those that occur in machine learning (ML), this approach produces a more optimum result than th ose produced by the state minimization alone. (C) 2001 Elsevier Science B.V . All rights reserved.