ALGORITHMS FOR AUTOMATIC DIALOG ANALYSIS USING PROPOSITIONAL PRODUCTION SYSTEMS

The specification of a graphical user interface (GUI), like any other part of a computer system, is an incremental process whereby an outlin e of the system is systematically developed, evaluated, and revised un til it is reasonably complete. This article describes some algorithms and procedures that can be used to automate the analysis of a specific ation to facilitate this iterative process. A propositional production system (PPS) is a notation that can be used by designers to describe the high-level behavior of a GUI. Such a description is executable and relatively easy to learn and use. PPSs are a form of state machine; t herefore, much of the theory of state machines can be applied to their analysis. PPSs, however, provide the advantage of semiparallel defini tions of state transitions. This is important, as dialogue models of m odern GUIs allow a large number of simultaneously available inputs lea ding to very large state spaces. By dealing in sets of states, a PPS m akes the problem of describing the potentially exponential number of s tate transitions tractable. This article discusses how this innovation can lead to efficient algorithms for analyzing a dialogue model for p roperties such as task completeness, reversibility of effect, accessib ility, connectedness, and avoidance of deadlock.