The paper first presents the dialogue system DIAL now being developed at the Centre de Recherche en Informatique de Nancy (CRIN). It then focusses on heuristic search problems related to the components in charge of parsing and interpretation, the syntactic-semantic component (SYNSEM) and the pragmatic component (DIALOG). After briefly outlining the operation of these components, we discuss two major types of heuristic search strategies in these components, selection strategies and propagation strategies.