Publication
A more bio-plausible approach to the evolutionary inference of finite state machines
AbstractWith resemblance of finite-state machines to some biological mechanisms in cells and numerous applications of finite automata in different fields, this paper uses analogies and metaphors to introduce an element of bio-plausibility to evolutionary grammatical inference. Inference of a finite-state machine that generalizes well over unseen input-output examples is an NP-complete problem. Heuristic algorithms exist to minimize the size of an FSM keeping it consistent with all the input-output sequences. However, their performance dramatically degrades in presence of noise in the training set. Evolutionary algorithms perform better for noisy data sets but they do not scale well and their performance drops as size or complexity of the target machine grows. Here, inspired by a biological perspective, an evolutionary algorithm with a novel representation and a new fitness function for inference of Moore finite-state machines of limited size is proposed and compared with one of the latest evolutionary techniques.
Download publicationRelated Resources
See what’s new.
01/01/2013
Net Promoter Scores and the Value of a Good User Experience
At Autodesk we’ve been using the Net Promoter method to analyze user…
01/01/1993
An Empirical Evaluation of Some Articulatory and Cognitive Aspects of Marking Menus
We describe marking menus, an extension of pie menus, which are well…
01/01/2014
An Investigation of Metrics For the in-situ Detection of Software Expertise
Task-based analysis is a common and effective way to measure expertise…
01/01/2015
Amphibious Envelope
This experimental building façade system re-imagines the insulated…
Get in touch
Something pique your interest? Get in touch if you’d like to learn more about Autodesk Research, our projects, people, and potential collaboration opportunities.
Contact us