Developing and integrating two lines of research, one focusing on discourse and the other on intention recognition in discourse, this paper presents the basic elements of a computational theory of discourse. The paper argues that by specifying the basic units a discourse comprises and the ways in which they can relate, an account of discourse structure provides the basis for an account of discourse meaning. It further notes that an account of discourse structure also plays a central role in language processing because it stipulates constraints on those portions of a discourse to which any given utterance in the discourse must be related. The first section of the paper states the main thesis of the paper, which is that the structure of any discourse is a composite of three distinct but interacting components: (1) the structure of the actual sequence of utterances in the discourse, (2) a structure of intentions, and (3) an attentional state. The second section examines the basic theory of discourse structure and presents an overview of each of the components of discourse structure, and the third section analyzes two sample discourses--a written text and a fragment of task-oriented dialogue--from the perspective of the theory being developed. The fourth section investigates various processing issues that the theory raises, while the fifth and sixth sections describe the role of the discourse structure components in explaining various properties of discourse. The seventh section describes the generalization from utterance-level to discourse-level intentions, establishes certain properties of the latter, and contrasts them with the rhetorical relations of alternative theories. The final section poses research questions suggested by the theory. (FL)