Minimal coverings for incompletely specified sequential machines
type: Item
instance of: scholarly article
title: Minimal coverings for incompletely specified sequential machines
zbMATH Open document ID: 0612.68051
DOI: 10.1007/BF00263650
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: In the literature the problem of finding minimal realizations for incompletely specified machines has been treated in a number of different ways. Solutions to this problem depend on the precise definition of what minimal realization means in this case. If the behaviour of a state is defined as its related partial input-output function then the behaviour of one machine A can cover the behaviour of another machine B if it contains better defined I/O functions for all states of B. Finding a minimal covering in this case is known to be NP-complete. We develop an algebraic treatment of the problem and give a homomorphic characterization of the covering-relation. The construction of state- splitting is also characterized as a special morphism. Then a heuristic method is proposed for finding minimal coverings.
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3990878
zbMATH Keywords: minimal realization
zbMATH Keywords: minimal covering
author: Bernd Reusch
author: Wolfgang Merzenich
MaRDI profile type: Publication
cites work: An Improved Method of Prime C-Class Derivation in the State Reduction of Sequential Networks
cites work: State Minimization of Incompletely Specified Sequential Machines
cites work: An Algebraic Method for Minimizing the Number of States in an Incomplete Sequential Machine
cites work: Simplification of Incompletely Specified Flow Tables with the Help of Prime Closed Sets
cites work: An Efficient State Minimization Algorithm for Some Special Classes of Incompletely Specified Sequential Machines
cites work: A Note on State Minimization of a Special Class of Incomplete Sequential Machines
cites work: On the Reduction of Superfluous States in a Sequential Machine
cites work: Connective Properties Preserved in Minimal State Machines
cites work: Compatibility of States in Input-Independent Machines
cites work: State Assignments in Combinational Networks
cites work: Minimal Closed Partitions for Incompletely Specified Flow Tables
cites work: A Discussion on Two Algorithms for Determining Maximum Compatibles
cites work: A New Rule for Reducing CC Tables
cites work: The Simplification of Sequential Machines with Input Restrictions
cites work: The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4
cites work: Extending the Definition of Prime Compatibility Classes of States in Incomplete Sequential Machine Reduction
cites work: Q5623602
cites work: State Reduction in Incompletely Specified Finite-State Machines
cites work: Minimal solutions of Paull-Unger problems
cites work: An Algebraic Proof of the Paull–Unger Theorem
cites work: Minimization of Incompletely Specified Sequential Machines
cites work: Further Comments on "Closure Partition Method for Minimizing Incomplete Sequential Machines"
cites work: Slave Memories and Dynamic Storage Allocation
cites work: A Decomposition Method of Determining Maximum Compatibles
cites work: Worst Case Bounds for Maximal Compatible Subsets
cites work: Q3886871
cites work: Q3257775
cites work: Sequential Algorithm for the Determination of Maximum Compatibles
cites work: Q5557943
cites work: Autonomous Clocks in Sequential Machines
cites work: A Method for Minimizing Incompletely Specified Sequential Machines
cites work: Closure Partition Method for Minimizing Incomplete Sequential Machines
cites work: Comments on "Closure Partition Method for Minimizing Incomplete Sequential Machines"
cites work: Q5606985
cites work: Partial abstract types
cites work: Q3929672
description: scientific article; zbMATH DE number 3990878