Computing and Information Systems - Theses

Permanent URI for this collection

Search Results

Now showing 1 - 10 of 18
  • Item
    Thumbnail Image
    Practical declarative debugging of mercury programs
    MacLarty, Ian Douglas. (University of Melbourne, 2006)
  • Item
    Thumbnail Image
    Practical declarative debugging of mercury programs
    MacLarty, Ian Douglas. (University of Melbourne, 2006)
  • Item
    Thumbnail Image
    Automatic instant messaging dialogue using statistical models and dialogue acts
    Ivanovic, Edward ( 2008)
    Instant messaging dialogue is used for communication by hundreds of millions of people worldwide, but has received relatively little attention in computational linguistics. We describe methods aimed at providing a shallow interpretation of messages sent via instant messaging. This is done by assigning labels known as dialogue acts to utterances within messages. Since messages may contain more than one utterance, we explore automatic message segmentation using combinations of parse trees and various statistical models to achieve high accuracy for both classification and segmentation tasks. Finally, we gauge the immediate usefulness of dialogue acts in conversation management by presenting a dialogue simulation program that uses dialogue acts to predict utterances during a conversation. The predictions are evaluated via qualitative means where we obtain very encouraging results.
  • Item
    Thumbnail Image
    The logic of bunched implications: a memoir
    Horsfall, Benjamin Robert ( 2006)
    This is a study of the semantics and proof theory of the logic of bunched implications (BI), which is promoted as a logic of (computational) resources, and is a foundational component of separation logic, an approach to program analysis. BI combines an additive, or intuitionistic, fragment with a multiplicative fragment. The additive fragment has full use of the structural rules of weakening and contraction, and the multiplicative fragment has none. Thus it contains two conjunctive and two implicative connectives. At various points, we illustrate a resource view of BI based upon the Kripke resource semantics. Our first original contribution is the formulation of a proof system for BI in the newly developed proof-theoretical formalism of the calculus of structures. The calculus of structures is distinguished by its employment of deep inference, but we already see deep inference in a limited form in the established proof theory for BI. We show that our system is sound with respect to the elementary Kripke resource semantics for BI, and complete with respect to a formulation of the partially-defined Kripke resource semantics. Our second contribution is the development from a semantic standpoint of preliminary ideas for a hybrid logic of bunched implications (HBI). We give a Kripke semantics for HBI in which nominal propositional atoms can be seen as names for resources, rather than as names for locations, as is the case with related proposals for BI-Loc and for intuitionistic hybrid logic.
  • Item
    Thumbnail Image
    Local search methods for constraint problems
    Muhammad, Muhammad Rafiq Bin ( 2008-02)
    This thesis investigates the use of local search methods in solving constraint problems. Such problems are very hard in general and local search offers a useful and successful alternative to existing techniques. The focus of the thesis is to analyze the techniques of invariants used in local search. The use of invariants have recently become the cornerstone of local search technology as they provide a declarative way to specify incremental algorithms. We have produced a series of program libraries in C++ known as the One-Way-Solver. The One-Way-Solver includes the implementation of incremental data structures and is a useful tool for the implementation of local search. The One-Way-Solver is applied to two challenging constraint problems, the Boolean Satisfiability Testing (SAT) and university course timetabling problems.
  • Item
    Thumbnail Image
    Using minimal recursion semantics in Japanese question answering
    DRIDAN, REBECCA ( 2006-09)
    Question answering is a research field with the aim of providing answers to a user’s question, phrased in natural language. In this thesis I explore some techniques used in question answering, working towards the twin goals of using deep linguistic knowledge robustly as well as using language-independent methods wherever possible. While the ultimate aim is cross-language question answering, in this research experiments are conducted over Japanese data, concentrating on factoid questions. The two main focus areas, identified as the two tasks most likely to benefit from linguistic knowledge, are question classification and answer extraction. In question classification, I investigate the issues involved in the two common methods used for this task—pattern matching and machine learning. I find that even with a small amount of training data (2000 questions), machine learning achieves better classification accuracy than pattern matching with much less effort. The other issue I explore in question classification is the classification accuracy possible with named entity taxonomies of different sizes and shapes. Results demonstrate that, although the accuracy decreases as the taxonomy size increases, the ability to use soft decision making techniques as well as high accuracies achieved in certain classes make larger, hierarchical taxonomies a viable option. For answer extraction, I use Robust Minimal Recursion Semantics (RMRS) as a sentence representation to determine similarity between questions and answers, and then use this similarity score, along with other information discovered during comparison, to score and rank answer candidates. Results were slightly disappointing, but close examination showed that 40% of errors were due to answer candidate extraction, and the scoring algorithm worked very well. Interestingly, despite the lower accuracy achieved during question classification, the larger named entity taxonomies allowed much better accuracy in answer extraction than the smaller taxonomies.
  • Item
    Thumbnail Image
    Improving the efficiency and capabilities of document structuring
    MARSHALL, ROBERT ( 2007)
    Natural language generation (NLG), the problem of creating human-readable documents by computer, is one of the major fields of research in computational linguistics The task of creating a document is extremely common in many fields of activity. Accordingly, there are many potential applications for NLG - almost any document creation task could potentially be automated by an NLG system. Advanced forms of NLG could also be used to generate a document in multiple languages, or as an output interface for other programs, which might ordinarily produce a less-manageable collection of data. They may also be able to create documents tailored to the needs of individual users. This thesis deals with document structure, a recent theory which describes those aspects of a document’s layout which affect its meaning. As well as its theoretical interest, it is a useful intermediate representation in the process of NLG. There is a well-defined process for generating a document structure using constraint programming. We show how this process can be made considerably more efficient. This in turn allows us to extend the document structuring task to allow for summarisation and finer control of the document layout. This thesis is organised as follows. Firstly, we review the necessary background material in both natural language processing and constraint programming.
  • Item
    Thumbnail Image
    On designing a mobile robot for RoboCup
    Peel, Andrew Gregory ( 2006-03)
    The Roobots are a robot soccer team which participated in the RoboCup small-sized robot league competition in the years 2000, 2001 and 2002, when they finished in fourth place. This thesis describes the design of the robots in the 2002 team. Design issues for mobile robots in the RoboCup small-sized robot league are reviewed. The design decisions are presented. Finally, some lessons learnt for system design and project management from the three years of competition are presented.
  • Item
    Thumbnail Image
    Agent-based approaches to pedestrian modelling
    RONALD, NICOLE AMY ( 2007-02)
    This thesis investigates the early stages of the software development process for agent-based models of pedestrian behaviour. Planning for pedestrians is becoming more important as planners and engineers become more aware of the sustainability and environmental aspects of transport and infrastructure. It is also necessary for the planning and management of pedestrian areas and events. Pedestrian behaviour is more difficult to model than other transport modes as it is not as constrained and operates at a finer scale. Many approaches have been developed for modelling pedestrian behaviour. The simplest involve a single mathematical equation taking into account area and attractiveness of an area to calculate the maximum capacity. More complicated mathematical models involving differential equations have also been used. Agent-based modelling is a recent development in modelling and simulation. These simulations contain agents who interact with each other and the environment in which they are situated. Their similarity to human societies has led to their use for many social applications. Many modellers are unsure of what agents are and how to develop models using them. In some cases, agents may be useful. In other cases, the model outputs and realism may not offset the learning curve, development time, and increased complexity of an agent-based model. (For complete abstract open document)
  • Item
    Thumbnail Image
    Shadowboard: an agent architecture for enacting a sophisticated digital self
    Goschnick, Steven Brady ( 2001-09)
    In recent years many people have built Personal Assistant Agents, Information Agents and the like, and have simply added them to the operating system as auxiliary applications, without regard to architecture. This thesis argues that an agent architecture, one designed as a sophisticated representation of an individual user, should be embedded deep in the device system software, with at least equal status to the GUI – the graphical user interface. A sophisticated model of the user is then built, drawing upon contemporary Analytical Psychology – the Psychology of Subselves. The Shadowboard Agent architecture is then built upon that user model, drawing both structural and computational implications from the underlying psychology. An XML DTD file named Shadowboard.dtd is declared as a practical manifestation of the semantics of Shadowboard. An implementation of the Shadowboard system is mapped out, via a planned conversion of two existing integrated systems: SlimWinX, an event-driven GUI system; and XSpaces, an object-oriented tuplespace system with Blackboard-like features. The decision making mechanism passes logic terms and contraints between the various sub-agent components (some of which take on the role of Constraint Solvers), giving this agent system some characteristics of a Generalised Constraint Solver. A Shadowboard agent (built using the system) consists of a central controlling autonomous agent named the Aware Ego Agent, and any number of sub-agents, which collectively form an integrated but singular whole agent modelled on the user called the Digital Self. One such whole-agent is defined in a file named DigitalSelf.xml – which conforms to the schema in Shadowboard.dtd - which offers a comprehensive and generic representation of a user’s stance in a 24x7 network, in particular - the Internet. Numerous types of Shadowboard sub-agents are declared.