Archives 

Show All

  • 2008
    • November
      • Boolean Affine Approximation with Binary Decision Diagrams
        11/10/08
        Title: Boolean Affine Approximation with Binary Decision Diagrams
        Authors: Kevin Henshall, Peter Schachte, Harald Sondergaard and Leigh Whiting
        Abstract:
        Selman and Kautz’s work on knowledge compilation has established how approximation (strengthening and/or weakening) of a propositio

      • Syntactic Conditions for Invertibility in Sequent Calculi
        11/05/08
        Title: Syntactic Conditions for Invertibility in Sequent Calculi
        Author: Peter Chapman
        Abstract:
        Formalised proofs of Cut admissibility sometimes rely on the invertibility of the rules of a sequent calculus. We present sufficient conditions for when a rule is invertible with respect

      • Reasoning about a distributed probabilistic system
        11/02/08
        Title: Reasoning about a distributed probabilistic system
        Authors: Ukachukwu Ndukwu, J.W. Sanders
        Abstract:
        Reasoning about a distributed system that exhibits a combination of probabilistic and temporal behaviour does not seem to be easy with current techniques. The reason is the int

      • On Process Complexity
        11/02/08
        Title: On Process Complexity
        Author: Adam Day
        Abstract:
        Process complexity is one of the basic variants of Kolmogorov complexity. Unlike plain Kolmogorov complexity, process complexity provides a simple characterization of randomness for real numbers in terms of initial segment comple

      • Edge-Selection Heuristics for Computing Tutte Polynomials
        11/02/08
        Title: Edge-Selection Heuristics for Computing Tutte Polynomials
        Authors: David Pearce, Gary Haggard, Gordon Royle
        Abstract:
        The Tutte polynomial of a graph, also known as the partition function of the q-state Potts model, is a 2-variable polynomial graph invariant of considerable imp

      • Linear Axis for Planar Straight Line Graphs
        11/02/08
        Title: Linear Axis for Planar Straight Line Graphs
        Author: Kira Vyatkina
        Abstract:
        A linear axis is a straight line skeleton for a polygonal shape. The concept of a linear axis \epsilon-equivalent to the medial axis has been introduced and studied for simple polygons and for those wit

      • Transformation Rules for Z
        11/02/08
        Title: Transformation Rules for Z
        Authors: Mark Utting, Petra Malik, Ian Toyn
        Abstract:
        Z is a formal speci cation language combining typed set theory, predicate calculus, and a schema calculus. This paper describes an extension of Z that allows transformation and reasoning rules to b

      • Longest Paths in Planar DAGs in Unambiguous Logspace
        11/02/08
        Title: Longest Paths in Planar DAGs in Unambiguous Logspace
        Authors: Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar.
        Abstract:
        Reachability and distance computation are known to be NL-complete in general graphs, but within UL \cap co-UL if the graphs are planar. However, finding lon

      • Formal Model of a Protocol Converter
        11/02/08
        Title: Formal Model of a Protocol Converter
        Authors: Jing Cao, Albert Nymeyer
        Abstract:
        Reuse of components is a burgeoning field in chip design. Shorter time to market and assured quality are just two good reasons to reuse previously engineered components. Problems arise however whe

      • Minimum Cost Homomorphism to Oriented Cycles with Some Loops
        11/02/08
        Title: Minimum Cost Homomorphism to Oriented Cycles with Some Loops
        Authors: Mehdi Karimi, Arvind Gupta
        Abstract:
        For digraphs D and H, a homomorphism of D to H is a mapping f : V (D) -> V(H) such that uv \in A(D) implies f(u)f(v) \in A(H). Suppose D and H are two digraphs, and c_i

      • Spreading of messages in random graphs
        11/02/08
        Title: Spreading of messages in random graphs
        Authors: Ching-Lueh Chang, Yuh-Dauh Lyuu
        Abstract:
        Chang and Lyuu [Chang and Lyuu, 2008] study the spreading of a message in an Erdos-Renyi random graph G(n, p) starting from a set of vertices that are convinced of the message initially. I

      • Distributing Frequency-Dependent Data Stream Computations
        11/02/08
        Title: Distributing Frequency-Dependent Data Stream Computations
        Author: Sumit Ganguly
        Abstract:
        For time-efficiency, data stream computations are often performed in a highly distributed fashion (e.g. internet applications and sensor networks). A distributed computation is modeled as

      • Papers
        11/02/08
        The authors of papers accepted for CATS 2009 were asked whether they wanted their paper to appear in the discussion track or not. The authors of 12 papers agreed to do so. All accepted papers, whether appearing in the discussion track or not, will appear in the CATS proceedings and will be allocated

      • CATS 2009 Discussion Track
        11/02/08
        Welcome to the CATS 2009 Discussion Track. This is a discussion forum for (some of) the accepted papers for CATS, which will be presented at the conference in Wellington in January, 2009. This forum will serve as a means of discussing these papers in the few months before the conference. Discussion