We present the results from a series of experiments aimed at uncovering the discourse structure of man-machine communication in natural language (Wizard of Oz experiments). The results suggest the existence of different classes of dialogue situations, requiring computational discourse representations of various complexity. Important factors seem to be the number of different permissible tasks in the system and to what extent the system takes initiative in the dialogue.