2009 Working Papers

Browse

Recent Submissions

  • Publication
    Seven abstraction rules preserving generalised nonblocking
    (Working Paper, University of Waikato, Department of Computer Science, 2009-09-01) Malik, Robi; Leduc, Ryan
    This working paper proposes a compositional approach to verify the generalised nonblocking property of discrete-event systems. Generalised nonblocking is introduced in [15] to overcome weaknesses of the standard nonblocking check in discrete-event systems and increase the scope of liveness properties that can be handled. This paper addresses the question of how generalised nonblocking can be verified efficiently. The explicit construction of the complete state space is avoided by first composing and simplifying individual components in ways that preserve generalised nonblocking. The paper extends and generalises previous results about compositional verification of standard nonblocking and lists a new set of computationally feasible abstraction rules for standard and generalised nonblocking.
  • Publication
    Linear-time graph triples census algorithm under assumptions typical of social networks
    (Journal Article, University of Waikato, Department of Computer Science, 2009-08-20) McEnnis, Daniel
    A graph triples census is a histogram of all possible sets of three vertici (called a triple) from a graph. Graph triples census have been in active use in sociology for over 50 years. The earliest paper using this approach is by Holland and Leinhardt [1]. This gives a general description of the structure of directed graphs in a fixed length vector. Since this time, this analytic tool has been widely used in social network analysis. A summary of important papers using this approach, both as end product and as a component of further analysis, are in[2].
  • Publication
    MIR task and evaluation techniques
    (Working Paper, University of Waikato, Department of Computer Science, 2009-08-12) McEnnis, Daniel
    Existing tasks in MIREX have traditionally focused on low-level MIR tasks working with flat (usually DSP-only) ground-truth. These evaluation techniques, however, can not evaluate the increasing number of algorithms that utilize relational data and are not currently utilizing the state of the art in evaluating ranked or ordered output. This paper summarizes the state of the art in evaluating relational ground-truth. These components are then synthesized into novel evaluation techniques that are then applied to 14 concrete music document retrieval tasks, demonstrating how these evaluation techniques can be applied in a practical context.
  • Publication
    Graph-RAT programming environment
    (Working Paper, University of Waikato, Department of Computer Science, 2009-08-12) McEnnis, Daniel
    Graph-RAT is a new programming environment specializing in relational data mining. It incorporates a number of different techniques into a single framework for data collection, data cleaning, propositionalization, and analysis. The language is functional where algorithms are executed over arbitrary sub-graphs of the data. Analytical results can be conducted using collaborative filtering or machine learning techniques. The example algorithms are under BSD license.
  • Publication
    A robust semantics hides fewer errors
    (Working Paper, University of Waikato, Department of Computer Science, 2009-06-10) Reeves, Steve; Streader, David
    In this paper we explore how formal models are interpreted and to what degree meaning is captured in the formal semantics and to what degree it remains in the informal interpretation of the semantics. By applying a robust approach to the definition of refinement and semantics, favoured by the event-based community, to state-based theory we are able to move some aspects from the informal interpretation into the formal semantics.
  • Publication
    Guarded operations, refinement and simulation
    (Working Paper, University of Waikato, Department of Computer Science, 2009-06-10) Reeves, Steve; Streader, David
    Simulation rules have long been used as an effective computational means to decide refinement relations in state-based formalisms. Here we investigate how they might be amended so as to decide the event-based notion of singleton failures refinement of abstract data types or processes that have operations with a "guarded" interpretation. As the results presented here and found elsewhere in the literature are so sensitive to the details of the definitions used, we have machine-checked our results.
  • Publication
    A semantics and implementation of a causal logic programming language
    (Working Paper, University of Waikato, Department of Computer Science, 2009-02-11) Cleary, John G.; Utting, Mark; Clayton, Roger
    The increasingly widespread availability of multicore and manycore computers demands new programming languages that make parallel programming dramatically easier and less error prone. This paper describes a semantics for a new class of declarative programming languages that support massive amounts of implicit parallelism.