This paper explores the possibility of using the evolution of a population of finite state machines (FSMs) as a measure of `randomness' of a given binary sequence. An FSM with binary input and output alphabet can be seen as a predictor of a binary sequence. For any finite binary sequence, there exists an FSM able to perfectly predict the string but such a predictor, in general, has a large number of states. In this paper, we address the problem of finding the best predictor for a given sequence. This is an optimization problem over the space of all possible FSMs with a fixed number of states evaluated on the considered sequence. For this optimization an evolutionary algorithm is used: the better the FSMs found are, the less `random' will the given sequence be.

Prediction of Binary Sequences by Evolving Finite State Machines

CERRUTI, Umberto;GIACOBINI, Mario Dante Lucio;
2002

Abstract

This paper explores the possibility of using the evolution of a population of finite state machines (FSMs) as a measure of `randomness' of a given binary sequence. An FSM with binary input and output alphabet can be seen as a predictor of a binary sequence. For any finite binary sequence, there exists an FSM able to perfectly predict the string but such a predictor, in general, has a large number of states. In this paper, we address the problem of finding the best predictor for a given sequence. This is an optimization problem over the space of all possible FSMs with a fixed number of states evaluated on the considered sequence. For this optimization an evolutionary algorithm is used: the better the FSMs found are, the less `random' will the given sequence be.
5th International Conference on Artificial Evolution
Le Creusot, France
October 2001
Proceedings of the 5th International Conference on Artificial Evolution
Springer Verlag
2310
42
53
pseudo-random sequence; evolutionary algorithm; prediction
Cerruti, Umberto; Giacobini, Mario Dante Lucio; Liardet, P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2318/5462
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact