UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

A more bio-plausible approach to the evolutionary inference of finite state machines

Shayani, H; Bentley, PJ; (2007) A more bio-plausible approach to the evolutionary inference of finite state machines. Presented at: UNSPECIFIED.

Full text not available from this repository.

Abstract

With 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. Copyright 2007 ACM.

Type: Conference item (UNSPECIFIED)
Title: A more bio-plausible approach to the evolutionary inference of finite state machines
ISBN: 159593698X
ISBN-13: 9781595936981
DOI: 10.1145/1274000.1274039
Keywords: Analogies, Bio-plausibility, Evolution, Evolutionary algorithms, Finite-state machine, Fsm, Genetic algorithms, Grammatical inference, Metaphors
UCL classification: UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/171573
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item