Alternatives to de Marcken:

(…various compression schemes, related to Lempel-Ziv…and)

1. Nevill-Manning (1996) Inferring Sequential Structure (student of Ian Witten)

Basic idea: scan the string, never permitting a repeat of a string of symbols. Whenever a repeat is found, replace it.

Input	Grammar
a	S -> a
ab	S -> ab
abc	S -> abc
abcd	S -> abcd
abcdb	S -> abcdb
abcdbc	S -> abcdbc	2 bc’s
	S-> aAdA; A->bc
abcdbca	S-> aAaAa; A->bc
abcdbcab	S-> aAdAab; A->bc
abcdbcabc	S-> aAdAabc; A->bc	2 bc’s
	S-> aAdAaA; A->bc	2 aA’s
	S-> BdAB; A->bc; B->aA
abcdbcabcd	S-> BdABd; A->bc; B->aA	2 Bd’s
	S-> CAC; A->bc; B->aA; C->Bd	B occurs only once on the rhs
	S-> CAC; A->bc; C->aAd