Search

While developments in 3D printing have opened up opportunities for improved access to graphical information for people who are blind or have low vision (BLV), they can provide only limited detailed and contextual information. Interactive 3D printed models (I3Ms) that provide audio labels and/or a conversational agent interface potentially overcome this limitation. We conducted a Wizard-of-Oz exploratory study to uncover the multi-modal interaction techniques that BLV people would like to use when exploring I3Ms, and investigated their attitudes towards different levels of model agency. These findings informed the creation of an I3M prototype of the solar system. A second user study with this model revealed a hierarchy of interaction, with BLV users preferring tactile exploration, followed by touch gestures to trigger audio labels, and then natural language to fill in knowledge gaps and confirm understanding., Paper presented at ACM CHI 2020: Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, ACM, New York, April 2020; Replacement: typos corrected

The Web and digital media require documents whose appearance and content adapt to the viewing context and to user interaction. While most previous research has focussed on adaptation for textual and multimedia content, this is also true for diagrammatic content. We (a) identify the reasons for adaptation and the different kinds of adaptation that make sense for diagrams; (b) present an aspect-oriented model for diagram adaptation that separates adaptation into different orthogonal components; (c) describe a diagram authoring tool based on this model; and (d) present the results of a user evaluation of the tool. Our model uses layout “configurations” to model significantly different layout alternatives and geometric constraints to perform minor layout adjustment. The author can also specify alternate representations for an object, alternate styles and alternate textual content. The resulting space of different versions of the diagram is the cross product of these different alternatives. At display time the version is selected from this cross product and constructed automatically, taking into account the author specified preference order on the alternatives, current viewing environment, and user interaction.

The emerging field of Immersive Analytics investigates how novel display and interaction technologies can enable people to better explore and analyse data and complex information. Collaboration is a crucial aspect of Immersive Analytics. In this paper we present ContextuWall, a system for interactive local and remote collaboration using touch and mobile devices as well as displays of various sizes. The system enables groups of users located on different sites to share content to a jointly used virtual desktop which is accessible over a secured network. This virtual desktop can be shown on different large displays simultaneously, taking advantage of their high resolution. To enable users to intuitively share, arrange as well as annotate image content, a purpose-built client software has been developed and can easily be adapted with plug-ins for existing data analytics software. We show exemplary use cases and describe the system architecture and its implementation.

Visualisations are commonly used to understand social, biological and other kinds of networks. Currently, we do not know how to effectively present network data to people who are blind or have low-vision (BLV). We ran a controlled study with 8 BLV participants comparing four tactile representations: organic node-link diagram, grid node-link diagram, adjacency matrix and braille list. We found that the node-link representations were preferred and more effective for path following and cluster identification while the matrix and list were better for adjacency tasks. This is broadly in line with findings for the corresponding visual representations., Comment: To appear in the ACM CHI Conference on Human Factors in Computing Systems (CHI 2020)

Access to information is a fundamental problem for people with vision impairment (PVI). Textual information are considerably more accessible with the use of screen readers that work on desktop and mobile devices. However, access to graphical information is still a challenging problem. There are different technologies to present graphics to PVI, but almost all of them suffer from practicality and portability. This paper describes the GraVVITAS (Graphics Viewer using Vibration Interactive Touch and Speech) framework which aims to be a complementary system for other assistive technologies; a solution that can be carried in one's pocket.

Showing flows of people and resources between multiple geographic locations is a challenging visualisation problem. We conducted two quantitative user studies to evaluate different visual representations for such dense many-to-many flows. In our first study we compared a bundled node-link flow map representation and OD Maps [37] with a new visualisation we call MapTrix. Like OD Maps, MapTrix overcomes the clutter associated with a traditional flow map while providing geographic embedding that is missing in standard OD matrix representations. We found that OD Maps and MapTrix had similar performance while bundled node-link flow map representations did not scale at all well. Our second study compared participant performance with OD Maps and MapTrix on larger data sets. Again performance was remarkably similar., Presented at IEEE Conference on Information Visualization (InfoVis 2016). Awarded Best Paper Honorable Mention. Part of PhD thesis arXiv:1908.00662

This paper presents the use of a projector-based spatial augmented reality system in an industrial quality assurance setting to highlight spot-weld locations on vehicle panels for manual welding operators. The aim of this work is to improve the precision and accuracy of manual spot-weld placements with the aid of visual cues as a proactive step by the automotive manufacturer to enhance product quality. The prototype system was deployed at General Motors (GM) Holden plant in Elizabeth, Australia on the production line building Holden Cruze vehicles. Production trials were conducted and techniques developed to analyse and validate the precision and accuracy of spot-welds both with and without the visual cues. A reduction of 52 % of the standard deviation of manual spot-weld placement was observed when using augmented reality visual cues. The average standard deviation with-AR assistance (19 panels and 114 spot-welds) was calculated at 1.94 mm compared to without-AR (45 panels and 270 spot-welds) at 4.08 mm. All welds were within the required specification and panels evaluated in this study were used as the final product made available to consumers. The visual cues enabled operators to spot-weld at a higher degree of precision and accuracy. Refereed/Peer-reviewed

We are developing an application to automatically generate an accessible graphic from a floor plan image. Floor plans generally contain large regions with functionally different sub-areas. A problem faced by visually impaired users in exploring such accessible floor plans is understanding the boundaries of these sub-areas. We present an effective method to partition such open plan areas. Initially, we conducted a formative user study to understand how people partition open plan areas. Based on the findings of the study, we identified a general set of guidelines for partitioning open plans. These guidelines were used to generate a set of candidate lines for sub-areas. An obstacle avoiding shortest-path Voronoi diagram was used to determine boundaries for each sub-area. Candidate lines such as wall extensions were automatically generated to replace the identified boundaries. We selected the best replacement for each boundary by scoring candidate lines using a set of criteria such as line length. Finally the proposed method was tested on a standard floor plan corpus using three novel measures.

The fields of operations research and computer science have long sought to find automatic solver techniques that can find high-quality solutions to difficult real-world optimisation problems. The traditional workflow is to exactly model the problem and then enter this model into a general-purpose “black-box” solver. In practice, however, many problems cannot be solved completely automatically, but require a “human-in-the-loop” to iteratively refine the model and give hints to the solver. In this paper, we explore the parallels between this interactive optimisation workflow and the visual analytics sense-making loop. We assert that interactive optimisation is essentially a visual analytics task and propose a problem-solving loop analogous to the sense-making loop. We explore these ideas through an in-depth analysis of a use-case in prostate brachytherapy, an application where interactive optimisation may be able to provide significant assistance to practitioners in creating prostate cancer treatment plans customised to each patient's tumour characteristics. However, current brachytherapy treatment planning is usually a careful, mostly manual process involving multiple professionals. We developed a prototype interactive optimisation tool for brachytherapy that goes beyond current practice in supporting focal therapy - targeting tumour cells directly rather than simply seeking coverage of the whole prostate gland. We conducted semi-structured interviews, in two stages, with seven radiation oncology professionals in order to establish whether they would prefer to use interactive optimisation for treatment planning and whether such a tool could improve their trust in the novel focal therapy approach and in machine generated solutions to the problem.

We explore the relative merits of matrix, node-link and combined side-by-side views for the visualisation of weighted networks with three controlled studies: (1) finding the most effective visual encoding for weighted edges in matrix representations; (2) comparing matrix, node-link and combined views for static weighted networks; and (3) comparing MatrixWave, Sankey and combined views of both for event-sequence data. Our studies underline that node-link and matrix views are suited to different analysis tasks. For the combined view, our studies show that there is a perceptually complementary effect in terms of improved accuracy for some tasks, but that there is a cost in terms of longer completion time than the faster of the two techniques alone. Eye-movement data shows that for many tasks participants strongly favour one of the two views, after trying both in the training phase.

High-quality immersive display technologies are becoming mainstream with the release of head-mounted displays (HMDs) such as the Oculus Rift. These devices potentially represent an affordable alternative to the more traditional, centralised CAVE-style immersive environments. One driver for the development of CAVE-style immersive environments has been collaborative sense-making. Despite this, there has been little research on the effectiveness of collaborative visualisation in CAVE-style facilities, especially with respect to abstract data visualisation tasks. Indeed, very few studies have focused on the use of these displays to explore and analyse abstract data such as networks and there have been no formal user studies investigating collaborative visualisation of abstract data in immersive environments. In this paper we present the results of the first such study. It explores the relative merits of HMD and CAVE-style immersive environments for collaborative analysis of network connectivity, a common and important task involving abstract data. We find significant differences between the two conditions in task completion time and the physical movements of the participants within the space: participants using the HMD were faster while the CAVE2 condition introduced an asymmetry in movement between collaborators. Otherwise, affordances for collaborative data analysis offered by the low-cost HMD condition were not found to be different for accuracy and communication with the CAVE2. These results are notable, given that the latest HMDs will soon be accessible (in terms of cost and potentially ubiquity) to a massive audience. Refereed/Peer-reviewed

This paper presents a context aware model for situated analytics, supporting a blended user interface. Our approach is a state-based model, allowing seamless transition between the physical space and information space during use. We designed the model to allow common user interface controls to work in tandem with the printed information on a physical object by adapting the operation and presentation based on a semantic matrix. We demonstrate the use of the model with a set of blended controls including; pinch zoom, menus, and details-on-demand. We analyze each control to highlight how the physical and virtual information spaces work in tandem to provide a rich interaction environment in augmented reality. Refereed/Peer-reviewed

The emerging field of Immersive Analytics investigates how novel display and interaction technologies can enable people to visualise and analyse data and complex information. In this paper, we present ContextuWall, a system for interactive local and remote collaboration using touch and mobile devices as well as displays of various sizes. The system enables groups of users located on different sites to share content to a jointly used virtual desktop which is accessible over a secured network. This virtual desktop can be shown on different large displays simultaneously, taking advantage of their high resolution. To enable users to intuitively share, arrange as well as annotate image content, a purpose-built client software has been built and can easily be adapted with plug-ins for existing data analytics software. We show exemplary use cases and describe the system architecture and its implementation.

We investigate the cognitive impact of various layout features-symmetry, alignment, collinearity, axis alignment and orthogonality - on the recall of network diagrams (graphs). This provides insight into how people internalize these diagrams and what features should or shouldn't be utilised when designing static and interactive network-based visualisations. Participants were asked to study, remember, and draw a series of small network diagrams, each drawn to emphasise a particular visual feature. The visual features were based on existing theories of perception, and the task enabled visual processing at the visceral level only. Our results strongly support the importance of visual features such as symmetry, collinearity and orthogonality, while not showing any significant impact for node-alignment or parallel edges.

We present a new model for presenting graphics in eBooks to blind readers. It is based on the GraViewer app which allows an accessible graphic embedded in an iBook to be explored on an iPad using speech and non-speech audio feedback. We also introduce a web-based tool, GraAuthor, for creating such accessible graphics and describe the workflow for including these in an iBook. Unlike previous approaches our model provides an integrated digital presentation of both text and graphics and allows the general public to create accessible graphics.

Recent constraint logic programming (CLP) languages, such as HAL and Mercury, require type, mode and determinism declarations for predicates. This information allows the generation of efficient target code and the detection of many errors at compile-time. Unfortunately, mode checking in such languages is difficult. One of the main reasons is that, for each predicate mode declaration, the compiler is required to appropriately re-order literals in the predicate's definition. The task is further complicated by the need to handle complex instantiations (which interact with type declarations and higher-order predicates) and automatic initialization of solver variables. Here we define mode checking for strongly typed CLP languages which require reordering of clause body literals. In addition, we show how to handle a simple case of polymorphic modes by using the corresponding polymorphic types., 46 pages, 3 figures To appear in Theory and Practice of Logic Programming

Eye-tracking equipment has proven useful in examining the cognitive processes people use when understanding and reasoning with visual stimuli. However, eye-tracking has several drawbacks: accurate eye-tracking equipment is expensive, it is often awkward for participants, it requires frequent recalibration, and the data can be difficult to interpret. We introduce an alternative tool: the Restricted Focus Viewer (RFV). This is a computer program that takes an image, blurs it, and displays it on a computer monitor, allowing the participant to see only a small region of the image in focus at any time. The region in focus can be moved using the computer mouse. The RFV records what the participant is focusing on at any point in time. It is cheap, nonintrusive, does not require calibration, and provides accurate data about which region is being focused on. We describe this tool and also provide experimental comparisons with eye-tracking. The RFV (Version 2.1) is freely available at http://www.csse.monash.edu. au/projects/RFV/.

Better access to on-line information graphics is a pressing need for people who are blind or have severe vision impairment. We present a new model for accessible presentation of on-line information graphics and demonstrate its use for presenting floor plans. While floor plans are increasingly provided on-line, people who are blind are at best provided with only a high-level textual description. This makes it difficult for them to understand the spatial arrangement of the objects on the floor plan. Our new approach provides users with significantly better access to such plans. The users can automatically generate an accessible version of a floor plan from an on-line floor plan image quickly and independently by using a web service. This generates a simplified graphic showing the rooms, walls, doors and windows in the original floor plan as well as a textual overview. The accessible floor plan is presented on an iPad using audio feedback. As the users touch graphic elements on the screen, the element they are touching is described by speech and non-speech audio in order to help them navigate the graphic.

More powerful personal computers and higher network bandwidth has meant that graphics has become increasingly important on the web. Graph-based diagrams are one of the most important types of structured graphical information. Here we demonstrate how XML can be used as the basis for contents-based delivery of graph-based diagrams. The main distinguishing feature of our approach is that it separates style and content of diagrams in the same way as (XML-based) markup languages for textual information do: The diagram itself is marked-up according to its logical structure and its visual appearance is defined via attached style sheets. Such an approach poses interesting challenges for the browser component, because it requires automatic layout of complex diagrammatic information that takes stylistic constraints into account. We present a prototype system for our approach comprised of three main components: a contents-based markup language, GXML, for specifying graph-based diagrams, a style sheet language, GXSL, for such diagrams and a browser that can display styled graphs from this information.

Researchers constantly read and annotate academic documents. While almost all documents are provided digitally, many are still printed and read on paper. We surveyed 162 academics in order to better understand their reading habits and preferences. We were particularly interested in understanding the barriers to digital reading and the features desired by academics for digital reading applications.

Information graphics are common in written communication. The ability to comprehend, use and create these graphics is an important skill that most of us take for granted. However, for those who are visually impaired, access to such graphics is severely limited. While new presentation technologies will improve access, an unsolved problem is how to automatically generate an accessible version of an information graphic. We describe the goals and approach of a project to develop software tools to do this. Our proposed approach uses advanced graphics recognition combined with high-level transformation. It is designed to handle a wide variety of information graphics, including floor plans, line graphs and organisation charts, and to be usable in schools, workplaces and at home.

Constraints can be used to specify declaratively the desired layout of a Web document. We present a system architecture in which both the author and the viewer can impose page layout constraints, some required and some preferential. The final appearance of the Web page is thus the result of negotiation between author and viewer, where this negotiation is carried out by solving the set of required and preferential constraints imposed by both parties. We identify two plausible system architectures, based on different ways of dividing the work of constraint solving between Web server and Web client. We describe a prototype constraint-based Web authoring system and viewing tool that provides linear arithmetic constraints for specifying the layout of the document as well as finite-domain constraints for specifying font size relationships. Finally, we provide an empirical evaluation of the prototype.

Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, by not really competitive with more conventional programming languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(ℛ). The compiler implements six powerful optimizations: reordering of constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

Program analysis based on abstract interpretation has proven very useful in compilation of constraint and logic programming languages. Unfortunately, the traditional goal-dependent framework is inherently imprecise. This is because it handles call and return in such a way that dataflow information may be re-asserted unnecessarily, leading to a loss of precision for many description domains. For a few specific domains, the literature contains proposals to overcome the problem, and some implementations use various unpublished tricks that sometimes avoid the precision loss. The purpose of this paper is to map the landscape of goal-dependent, goal-independent, and combined approaches to generic analysis of logic programs. This includes formalising existing methods and tricks in a way that is independent of specific description domains. Moreover, we suggest new methods for overcoming the loss of precision — altogether eight different semantics are considered and compared. We provide theoretical results determining the relative accuracy of the approaches. These show that two of our new semantics are uniformly more accurate than existing approaches. Experiments that we have performed (for two description domains) with implementations of the eight different approaches enable a discussion of their relative runtime performances. We discuss the expected effect on other domains as well and conclude that our new methods can be trusted to yield significantly more accurate analysis for a small extra implementation effort, without compromising the efficiency of analysis.

The incorporation of global program analysis into recent compilers for Constraint Logic Programming (CLP) languages has greatly improved the efficiency of compiled programs. We present a global analyser based on abstract interpretation. Unlike traditional optimizers, whose designs tend to be ad hoc, the analyser has been designed with flexibility in mind. The analyser is incremental, allowing substantial program transformations by a compiler without requiring redundant re-computation of analysis data. The analyser is also generic in that it can perform a large number of different program analyses. Furthermore, the analyser has an object-oriented design, enabling it to be adapted to different applications easily and allowing it to be used with various CLP languages with simple modifications. As an example of this generality, we sketch the use of the analyser in two different applications involving two distinct CLP languages: an optimizing compiler for CLP(R) programs and an application for detecting occur-check problems in Prolog programs. © 1998 by John Wiley & Sons Ltd.

Visual language specification has been investigated for more than two decades now and many different formalisms for specifying and parsing visual languages have been invented. However, there has been little attempt to develop a systematic and comprehensive hierarchy of visual languages based on their formal properties. Given the importance of the Chomsky hierarchy for the theory of textual languages and the difficulty of comparing these many different visual language formalisms, it is clear that there is a need for such a hierarchy. We develop a hierarchy for visual languages and investigate the expressiveness and cost of parsing for classes defined therein. Although the hierarchy is based on the constraint multiset grammar formalism, we sketch how other visual language specification formalisms can be mapped into constraint multiset grammars so that a comparison is made possible. One consequence of our work is that a large class of ‘naturally occurring’ visual languages are inherently context-sensitive, so that the core of such a hierarchy has to be built around different forms of context-sensitivity.

The first logic programming languages, such as Prolog, used a fixed left-to-right atom scheduling rule. Unfortunately, this meant that programs written in a clean, declarative style were often very inefficient, only terminated when certain inputs were fully instantiated or “ground,” and (if negation was used) produced wrong results. For this reason, nearly all recent logic programming languages provide more flexible scheduling in which computation generally proceeds left-to-right but in which some calls are dynamically “delayed” until their arguments are sufficiently instantiated to allow the call to run efficiently. Despite the increasing practical importance of logic programming languages with dynamic scheduling, relatively little attention has been paid to their semantics. We lift the standard algebraic and logical soundness and completeness results for success and finite failure for constraint logic programs to constraint logic programming languages with dynamic scheduling. The proofs are quite simple and essentially rely on treating the delayed calls as part of the answer constraint.

Confluence is an important and desirable property as it allows the program to be understood by considering any desired scheduling rule, rather than having to consider all possible schedulings. Unfortunately, the usual operational semantics for concurrent constraint programs is not confluent as different process schedulings give rise to different sets of possible outcomes. We show that it is possible to give a natural confluent calculus for concurrent constraint programs, if the syntactic domain is extended by a blind choice operator and a special constant standing for a discarded branch. This has application to program analysis.

The standard operational semantics of concurrent constraint logic languages is not confluent in the sense that different schedulings of processes may result in different program behaviors. While implementations are free to choose specific scheduling policies, analyses should be correct for all implementations. Moreover, in the presence of parallelism, it is usually not possible to determine how processes will actually be scheduled. Efficient program analysis is therefore difficult as all process schedulings must be considered. To overcome this problem, we introduce a confluent semantics which closely approximates the standard (nonconfluent) semantics. This semantics provides a basis for efficient and accurate program analysis for these languages. To illustrate the usefulness of this approach, we sketch analyses based on abstract interpretations of the confluent semantics which determine if a program is suspension- and local suspension-free.

Typesetting software is often faced with conflicting aesthetic goals. For example, choosing where to break lines in text might involve aiming to minimize hyphenation, variation in word spacing, and consecutive lines starting with the same word. Typically, automatic layout is modelled as an optimization problem in which the goal is to minimize a complex objective function that combines various penalty functions each of which corresponds to a particular bad feature. Determining how to combine these penalty functions is difficult and very time consuming, becoming harder each time we add another penalty. Here we present a machine-learning approach to do this, and test it in the context of line-breaking. Our approach repeatedly queries the expert typographer as to which one of a pair of layouts is better, and accordingly refines the estimate of how best to weight the penalties in a linear combination. It chooses layout pair queries by a heuristic to maximize the amount that can be learnt from them so as to reduce the number of combinations that must be considered by the typographer.

Guillotine-based page layout is a method for document layout commonly used by newspapers and magazines, where each region of the page either contains a single article, or is recursively split either vertically or horizontally. Suprisingly there appears to be little research into algorithms for automatic guillotine-based document layout. In this paper we give efficient algorithms to find optimal solutions to guillotine layout problems of two forms. Fixed-cut layout is where the structure of the guillotining is given and we only have to determine the best configuration for each individual article to give the optimal total configuration. Free layout is where we also have to search for the optimal structure. We give bottom-up and top-down dynamic programming algorithms to solve these problems, and propose a novel interaction model for documents on electronic media. Experiments show that our algorithms are effective for realistic layout problems.

Graphics are widely used in newspapers, text books, web pages, metro maps, instruction manuals etc. When appropriate they can provide significant cognitive benefits over text. Their use is set to increase as interactive information visualisation applications become more mainstream.

Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies . However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.

Logic-programming languages are based on a principle of separation “logic” and “control.”. This means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof procedure, viewing execution as theorem proving). Although the separation is desirable from a semantical point of view, it makes sound, efficient implementation of logic-programming languages difficult. The lack of “control information” in programs calls for complex data-flow analysis techniques to guide execution. Since data-flow analysis furthermore finds extensive use in error-finding and transformation tools, there is a need for a simple and powerful theory of data-flow analysis of logic programs. This paper offers such a theory, based on F. Nielson's extension of P. Cousot and R. Cousot's abstract interpretation . We present a denotational definition of the semantics of definite logic programs. This definition is of interest in its own right because of its compactness. Stepwise we develop the definition into a generic data-flow analysis that encompasses a large class of data-flow analyses based on the SLD execution model. We exemplify one instance of the definition by developing a provably correct groundness analysis to predict how variables may be bound to ground terms during execution. We also discuss implementation issues and related work.

Access to graphics and other two dimensional information is still severely limited for people who are blind. We present a new multimodal computer tool, GraVVITAS, for presenting accessible graphics. It uses a multitouch display for tracking the position of the user's fingers augmented with haptic feedback for the fingers provided by small vibrating motors, and audio feedback for navigation and to provide non-geometric information about graphic elements. We believe GraVVITAS is the first practical, generic, low cost approach to providing refreshable accessible graphics. We have used a participatory design process with blind participants and a final evaluation of the tool shows that they can use it to understand a variety of graphics - tables, line graphs, and floorplans.

Difference-lists are terms that represent lists. The use of difference-lists can speed up most list-processing programs considerably. Prolog programmers routinely use “difference-list versions” of programs, but very little investigation has taken place into difference-list transformation. Thus, to most programmers it is either unknown that the use of difference-lists is far from safe in all contexts, or else this fact is known but attributed to Prolog’s infamous “occur check problem.” In this paper we study the transformation of list-processing programs into programs that use differencelists. In particular we are concerned with finding circumstances under which the transformation is safe. We show that dataflow analysis can be used to determine whether the transformation is applicable to a given program, thereby allowing for automatic transformation. We prove that our transformation preserves strong operational equivalence.

Many applications of constraint logic programming (CLP) languages require not only testing if a set of constraints is satisfiable, but also finding the optimal solution which satisfies them. Unfortunately, the standard declarative semantics for CLP languages does not consider optimization but only constraint satisfaction. Here we give a model theoretic semantics for optimization, which is a simple extension of the standard semantics, and a corresponding operational semantics, which may be efficiently implemented.

interpretation theory provides a semantic foundation for dataflow analysis of programs by formalizing the relationship between analysis and semantics. In the original theory for abstract interpretation, due to Cousot and Cousot, this relationship was given in terms of an adjoined pair of functions. One function, called the abstraction function, mapped data to their best description, while the second function, called the concretization function, mapped descriptions to the largest data object they described. Since this time, however, a number of other “frameworks” for abstract interpretation have been developed, differing in how the descriptions are related to the actual data used in computation. For instance, one framework uses only abstraction functions, another uses only concretization functions, while yet another allows an arbitrary approximation relation. We illustrate that each of these frameworks has certain advantages and limitations. This motivates our development and study of a general framework which encompasses these other approaches. We examine this framework with regard to three questions: when does approximation lift from base functions to all expressions; when is approximation transitive; and when is there an optimal approximation and how can it be inferred? Answers to these questions are not only interesting in the context of our framework but also provide a better understanding of the other frameworks.

We review the literature on automatic document formatting with an emphasis on recent work in the field. One common way to frame document formatting is as a constrained optimization problem where decision variables encode element placement, constraints enforce required geometric relationships, and the objective function measures layout quality. We present existing research using this framework, describing the kind of optimization problem being solved and the basic optimization techniques used to solve it. Our review focuses on the formatting of primarily textual documents, including both micro- and macro-typographic concerns. We also cover techniques for automatic table layout. Related problems such as widget and diagram layout, as well as temporal layout issues that arise in multimedia documents are outside the scope of this review.

Digital whiteboards promise to revolutionize the delivery of educational material. Like a traditional whiteboard, they support spontaneous and interactive teaching by allowing free-form editing and scribbling. However, digital whiteboards also allow seamless integration of multi-media content and fit naturally into a web-based teaching environment. The eChalk system has been built to support on-line teaching with digital whiteboards in a university environment. An important feature of eChalk is that hand drawn input is automatically interpreted. This allows sketching and scribbling to be used as an interface to powerful back-end applications. eChalk also allows sketches and scribbles to be transcribed into semantic formats suited to flexible delivery. However, at present developing automatic sketch interpretation engines is extremely time consuming. We describe how we have extended the eChalk system with a generic diagram interpretation component that makes development of new applications considerably faster and easier.

A key issue in visual languages is the specification of the relationship between pictures and their meaning. To do this, we introduce a class of declarative, constraint-based picture specification languages. These extend previous approaches to picture specification based on constraints and grammar formalisms. As the languages are defined as instances of an abstract language scheme, we ensure they share a common declarative semantics and operational semantics. The declarative semantics allows both people and machines easily to reason about a specification independently of any underlying implementation. The operational semantics permit both the generation and recognition of pictures defined by the specification.

We have implemented a Java application that automatically generates tactile bar and pie charts from data values given in a formatted text file. The tool is designed to semi-automate the construction of tactile versions of bar and pie charts in educational material. The tool provides a wide variety of layout styles. While the tool allows the user to fine tune the layout, the generated SVG diagram can also be modified in a standard diagram editor.

Computer understanding of visual languages in pen-based environments requires a combination of lexical analysis in which the basic tokens are recognized from hand-drawn gestures and syntax analysis in which the structure is recognized. Typically, lexical analysis relies on statistical methods while syntax analysis utilizes grammars. The two stages are not independent: contextual information provided by syntax analysis is required for lexical disambiguation. Previous research into visual language recognition has focussed on syntax analysis while relatively little research has been devoted to lexical analysis and its integration with syntax analysis. This paper describes GestureLab, a tool designed for building domain-specific gesture recognizers, and its integration with Cider, a grammar engine that uses GestureLab recognizers and parses visual languages. Recognizers created with GestureLab perform probabilistic lexical recognition with disambiguation occurring during parsing based on contextual syntactic information. Creating domain-specific gesture recognizers is not a simple task. It requires significant amounts of experimentation and training with large gesture corpora to determine a suitable set of features and classifier algorithm. GestureLab supports such experimentation and facilitates collaboration by allowing corpora to be shared via remote databases.

We describe a small, non-intrusive extension to the declarative modelling language Zinc that allows users to define model-specific search. This is achieved by providing a number of generic search patterns that take Zinc user-defined functions as parameters. We show the generality of the approach by using it to implement three very different kinds of search: backtracking search, branch-and-bound search, and local search. Our approach is competitive with hand-coded search strategies.

We describe the Zinc modelling language. Zinc provides set constraints, user defined types, constrained types, and polymorphic predicates and functions. The last allows Zinc to be readily extended to different application domains by user-defined libraries. Zinc is designed to support a modelling methodology in which the same conceptual model can be automatically mapped into different design models, thus allowing modellers to easily “plug and play” with different solving techniques and so choose the most appropriate for that problem.

We describe a preliminary implementation of the high-level modelling language Zinc. This language supports a modelling methodology in which the same Zinc model can be automatically mapped into different design models, thus allowing modellers to easily “plug and play” with different solving techniques and so choose the most appropriate for that problem. Currently, mappings to three very different design models based on constraint programming (CP), mixed integer programming (MIP) and local search are provided. Zinc is the first modelling language that we know of that supports such solver and technique-independent modelling. It does this by using an intermediate language called Flattened Zinc, and rewrite rules for transforming the Flattened Zinc model into one that is tailored to a particular solving technique.

The G12 project recently started by National ICT Australia (NICTA)is an ambitious project to develop a software platform for solving large scale industrial combinatorial optimisation problems. The core design involves three languages: Zinc, Cadmium and Mercury (Group 12 of the periodic table). Zinc is a declarative modelling language for expressing problems, independent of any solving methodology. Cadmium is a mapping language for mapping Zinc models to underlying solvers and/or search strategies, including hybrid approaches. Finally, existing Mercury will be extended as a language for building extensible and hybridizable solvers. The same Zinc model, used with different Cadmium mappings, will allow us to experiment with different complete, local, or hybrid search approaches for the same problem. This talk will explain the G12 global design, the final G12 objectives, and our progress so far.