Contributions of formal language theory to the study of dialogues

Abstract

For more than 30 years, the problem of providing a formal framework for modeling dialogues has been a topic of great interest for the scienti&#64257;c areas of Linguistics, Philosophy, Cognitive Science, Formal Languages, Software Engineering and Arti&#64257;cial Intelligence. In the beginning the goal was to develop a "conversational computer", an automated system that could engage in a conversation in the same way as humans do. After studies showed the di&#64259;culties of achieving this goal Formal Language Theory and Arti&#64257;cial Intelligence have contributed to Dialogue Theory with the study and simulation of machine to machine and human to machine dialogues inspired by Linguistic studies of human interactions. <br/>The aim of our thesis is to propose a formal approach for the study of dialogues. Our work is an interdisciplinary one that connects theories and results in Dialogue Theory mainly from Formal Language Theory, but also from another areas like Arti&#64257;cial Intelligence, Linguistics and Multiprogramming. <br/>We contribute to Dialogue Theory by introducing a hierarchy of formal frameworks for the de&#64257;nition of protocols for dialogue interaction. Each framework de&#64257;nes a transition system in which dialogue protocols might be uniformly expressed and compared. The frameworks we propose are based on &#64257;nite state transition systems and Grammar systems from Formal Language Theory and a multi-agent language for the speci&#64257;cation of dialogue protocols from Arti&#64257;cial Intelligence. Grammar System Theory is a sub&#64257;eld of Formal Language Theory that studies how several (a &#64257;nite number) of language de&#64257;ning devices (language processors or grammars) jointly develop a common symbolic environment (a string or a &#64257;nite set of strings) by the application of language operations (for instance rewriting rules). For the frameworks we propose we study some of their formal properties, we compare their expressiveness, we investigate their practical application in Dialogue Theory and we analyze their connection with theories of human-like conversation from Linguistics. <br/>In addition we contribute to Grammar System Theory by proposing a new approach for the veri&#64257;cation and derivation of Grammar systems. We analyze possible advantages of interpreting grammars as multiprograms that are susceptible of veri&#64257;cation and derivation using the Owicki-Gries logic, a Hoare-based logic from the Multiprogramming &#64257;eld.