SAMVAAD: Speech Application Made Viable For Access-Anywhere Devices

The proliferation of pervasive devices calls for the enablement of ubiquitous access via multiple modalities. Since the capabilities of pervasive devices differ vastly, device-specific application adaptation becomes a necessity. We address the problem of speech application adaptation by dialog call-flow reorganisation for pervasive devices with different memory constraints. One usability criterion we use is minimising the number of dialogs in the call-flow. Given an atomic dialog call-flow C and memory size m, we present optimal algorithms, RESEQUENCE and BALANCETREE, that output the corresponding reorganised version Cm, such that the number of questions (prompts) is minimum. In some cases, an ‘ideal’ reference call-flow that takes into account various usability criteria may be available. In such cases, minimising the number of changes to this ideal call-flow to accommodate memory-constrained devices forms another ‘usability criterion’. We present two algorithms, MASQ and MATREE that minimise the distance from the ideal call-flow.
The following observation forms the cornerstone of all the algorithms in this paper: Two grammars g1 and g2 comprising of |g1| and |g2| elements respectively can be merged into a single grammar g = g1 X g2 having |g1|.|g2| elements for the sequential case, and g = g1 + g2 having |g1|+|g2| elements for the tree case.
We introduce the concept of an <m,q>-characterisation of a call-flow, defined as the set of pairs { (mi, qi) | i c N }, where qi is the minimum number of questions required for memory size mi. Each call-flow has a unique, device-independent signature in its <m,q>-characterisation, which provides a means for comparing call-flows from an adaptation standpoint.