On the Synthesis of Finite-State Machines from Samples of Their Behavior

1972/06/01 by A. W. Biermann, Alan W. Biermann, J. A. Feldman +1 · 9 citations
Computer Science · #semigroups and automata theory #Machine Learning and Algorithms #Algorithms and Data Compression

paper · doi:10.1109/tc.1972.5009015

Abstract

The Nerode realization technique for synthesizing finite-state machines from their associated right-invariant equivalence relations is modified to give a method for synthesizing machines from finite subsets of their input-output behavior. The synthesis procedure includes a parameter that one may adjust to obtain machines that represent the desired behavior with varying degrees of accuracy and that consequently have varying complexities. We discuss some of the uses of the method, including an application to a sequential learning problem.

Citations

• Derivatives of Regular Expressions

Cited by

• Minimal History-Deterministic Co-Büchi Automata: Congruences and Passive Learning
• Mining State-Based Models from Proof Corpora
• Mining Service Behavior for Stateful Service Emulation
• Inference of Deterministic Finite Automata via Q-Learning
• SysMoBench: Evaluating AI on Formally Modeling Complex Real-World Systems
• Specification Mining for Smart Contracts with Automatic Abstraction Tuning
• Passive Model Learning of Visibly Deterministic Context-free Grammars
• Scalable Inference of System-level Models from Component Logs
• PRINS: scalable model inference for component-based system logs. [europepmc]

Related

• Finite State Machine Synthesis for Evolutionary Hardware
• An Input-Output Construction of Finite State ρ/μ Approximations for Control Design
• Synthesis of Procedural Models for Deterministic Transition Systems
• Synthesis of Binary k-Stage Machines
• Bounded Cycle Synthesis