An Extension and Formalization of a Specification Language for Mixed-Initiative, Human-Computer Dialogues

Date of Award


Degree Name

M.C.S. in Computer Science


Department of Computer Science


Saverio Perugini


The use of human-computer dialogue is playing an increasingly prominent role in interactions conducted at kiosks (e.g., withdrawing money from an ATM), on smart phones (e.g., booking a flight), and on the web (e.g., customer service chatbots). Some human-computer dialogues involve a lively exchange of system-initiated and user-initiated actions. These dialogues are called mixed-initiative dialogues and also sometimes involve the pursuit of multiple sub-dialogue threads at once, which are woven together in a manner akin to concurrently executing threads. However, existing dialogue specification languages have difficulty expressing these dialogues concisely. In this work, we improve the expressiveness of a dialogue authoring language based on programming language concepts (e.g., curried functions) by augmenting it with additional high-level abstractions to support concise specification of task-based, mixed-initiative dialogues that resemble concurrently executing threads. We also formalize the process of simplifying and staging such dialogues specified in the augmented language using notions from discrete mathematics. We demonstrate that dialogue specifications written in the original authoring language can be compressed by rewriting them using the new abstractions. We also operationalize the formally specified dialogue simplification and staging rules in a Haskell programming implementation. The augmented dialogue authoring language is evaluated from practical (i.e., case study), conceptual (i.e., comparisons to similar systems such as VoiceXML), and theoretical perspectives. The results indicate that the augmented language enables concise representation of dialogues composed of multiple concurrent sub-dialogues and improves the compression of dialogue expressions reported in prior research. The Haskell implementation of the simplification/staging rules provides a proof of concept that the formal semantics are sufficient to implement a dialogue system specified with the augmented language.


Computer Science, human-computer interaction, dialogue systems, task-based, mixed-initiative, formal semantics

Rights Statement

Copyright © 2022, author.