Iterative minimization of partial finite state machines
Abstract: Finite state machines have been used in many contexts, e.g., test generation, system modeling, language processing. In these applications, the size of the machine has a great impact on the complexity and quality of the results. Thus, it is desirable to obtain a machine without redundant states, i.e., to minimize the machine. However, the minimization of partially specified finite state machines is a known NP-complete problem, and many heuristics to obtain feasible solutions have been proposed. In this paper, we propose an approach to minimize partial finite state machines based on the selection of compatible states using maximum cliques on the distinction graph. We experimented with our method comparing it with previous methods and the data suggest that our approach is more efficient, generating good results in less time.
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Bibliographic citation
-
Iterative minimization of partial finite state machines ; volume:3 ; number:2 ; year:2013 ; pages:91-103 ; extent:13
Open computer science ; 3, Heft 2 (2013), 91-103 (gesamt 13)
- Creator
-
Alberto, Alex
Simao, Adenilso
- DOI
-
10.2478/s13537-013-0106-0
- URN
-
urn:nbn:de:101:1-2410301517251.400744569622
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
15.08.2025, 7:39 AM CEST
Data provider
This object is provided by:
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Alberto, Alex
- Simao, Adenilso
Other Objects (12)
Iterative approximation of solutions for constrained convex minimization problem
Aggregation-based minimization of finite state automata
Iterative methods for constrained convex minimization problem in Hilbert spaces
Iterative regularization for constrained minimization formulations of nonlinear inverse problems
An iterative algorithm to bound partial moments
Online makespan minimization for MapReduce scheduling on multiple parallel machines
Iterative Differential Equations and Finite Groups
Optimal partial clique edge covering guided by potential energy minimization
Iterative algorithms for monotone inclusion problems, fixed point problems and minimization problems
Compositional minimization of finite state systems using interface specifications
Finite element discretization and iterative solution of total variation regularized minimization problems and application to the simulation of rate-independent damage evolutions
Iterative arrays with finite inter-cell communication
Iterative approximation of solutions for constrained convex minimization problem
Aggregation-based minimization of finite state automata
Iterative methods for constrained convex minimization problem in Hilbert spaces
Iterative regularization for constrained minimization formulations of nonlinear inverse problems
An iterative algorithm to bound partial moments
Online makespan minimization for MapReduce scheduling on multiple parallel machines
Iterative Differential Equations and Finite Groups
Optimal partial clique edge covering guided by potential energy minimization
Iterative algorithms for monotone inclusion problems, fixed point problems and minimization problems
Compositional minimization of finite state systems using interface specifications
Finite element discretization and iterative solution of total variation regularized minimization problems and application to the simulation of rate-independent damage evolutions
Iterative arrays with finite inter-cell communication
Iterative approximation of solutions for constrained convex minimization problem
Aggregation-based minimization of finite state automata
Iterative methods for constrained convex minimization problem in Hilbert spaces
Iterative regularization for constrained minimization formulations of nonlinear inverse problems
An iterative algorithm to bound partial moments
Online makespan minimization for MapReduce scheduling on multiple parallel machines
Iterative Differential Equations and Finite Groups
Optimal partial clique edge covering guided by potential energy minimization
Iterative algorithms for monotone inclusion problems, fixed point problems and minimization problems
Compositional minimization of finite state systems using interface specifications
Finite element discretization and iterative solution of total variation regularized minimization problems and application to the simulation of rate-independent damage evolutions