A new type of Markovian sequence generator and generation method generates a Markovian sequence having controllable properties, notably properties that satisfy at least one control criterion which is a computable requirement holding on items in the sequence. The Markovian sequence is generated chunkwise, each chunk containing a plurality of items in the sequence. During generation of each chunk a search is performed in the space of Markovian sequences to find a chunk-sized series of items which enables the control criterion to be satisfied. The search can be performed using a generate and test approach in which chunk-sized Markovian sequences are generated then tested for compliance with the requirement(s) of the control criteria. Alternatively, the search can be performed by formulating the sequence-generation task as a constraint satisfaction problem, with one or more constraints ensuring that the generated sequence is Markovian and one or more constraints enforcing the requirement(s) of the control criteria. The sequence generator can be used in an interactive system where a user specifies the control criterion via an inputting device (20).