1996:
Melbourne, Victoria, Australia (Chair: Peter Eades)
1994:
Sydney, NSW, Australia (Chair: Barry Jay)
CATS 2009 Wellington
program committee:
Rod Downey, Victoria University of Wellington, NZ (Co-chair);
Prabhu Manyem, University of Ballarat, Australia (Co-chair);
James Harland, RMIT University at Melbourne, Australia (Discussion Track coordinator);
Eric Allender, Rutgers University, New Jersey, USA;
Argimiro Arratia, University of Valladolid, Spain;
Hajo Broersma, University of Durham, UK;
Otfried Cheong, Korea Advanced Institute of Science and Technology at Daejeon, South Korea;
Jeremy Dawson, Australian National University at Canberra;
Thomas Erlebach, University of Leicester, UK;
Mike Johnson, Macquarie University at Sydney, Australia;
Bakhadyr Khoussainov, University of Auckland (NZ) and Cornell University (USA);
Catherine McCartin, Massey University at Palmerston North, NZ;
Kamal Lodaya, The Institute of Mathematical Sciences, Chennai, India;
James Noble, Victoria University of Wellington, NZ;
Paritosh Pandya, Tata Institute of Fundamental Research, Mumbai, India;
Frank Ruskey, University of Victoria, BC, Canada;
Stefan Szeider, University of Durham, UK;
Richard Taylor, Defence Science and Technology Organisation at Canberra, Australia;
Hans van Ditmarsch, University of Otago at Dunedin, NZ;
Tasos Viglas, University of Sydney, Australia;
accepted papers:
Ching-Lueh Chang and Yuh-Dauh Lyuu. reading of messages in random graphs (STUDENT PAPER);
Mehdi Karimi and Arvind Gupta. Minimum Cost Homomorphism to Oriented Cycles with Some Loops (STUDENT PAPER);
Wataru Matsubara, Shunsuke Inenaga and Ayumi Shinohara. Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program (STUDENT PAPER);
Adam Day. On Process Complexity (BEST STUDENT PAPER);
Ukachukwu Ndukwu and J.W. Sanders. Reasoning about a distributed probabilistic system (STUDENT PAPER);
Toshimasa Ishii and Kazuhisa Makino. Augmenting Edge-Connectivity between Vertex Subsets;
Abusayeed Saifullah and Alper Ungor. A Simple Algorithm For Triconnectivity of a Multigraph;
Koji Nakazawa and Makoto Tatsuta. Type Checking and Inference for Polymorphic and Existential types;
Mark Utting, Petra Malik and Ian Toyn. Transformation Rules for Z;
Vlad Estivill-Castro and Mahdi Parsa. Computing Nash equilibria gets harder: New results show hardness even for Parameterized Complexity;
Hideaki Fukuhara and Eiji Takimoto. Lower bounds on quantum query complexity for read-once decision trees with parity nodes (STUDENT PAPER);
Nutan Limaye, Meena Mahajan and Prajakta Nimbhorkar. Longest Paths in Planar DAGs in Unambiguous Logspace (STUDENT PAPER);
Jing Cao and Albert Nymeyer. Formal Model of a Protocol Converter (STUDENT PAPER);
Kevin Henshall, Peter Schachte, Harald Sondergaard and Leigh Whiting. Boolean Affine Approximation with Binary Decision Diagrams;
Andras Farago. Structural Properties of Random Graph Models;
Kira Vyatkina. Linear Axis for Planar Straight Line Graphs;
David Pearce, Gary Haggard and Gordon Royle. Edge-Selection Heuristics for Computing Tutte Polynomials;
Sumit Ganguly. Distributing Frequency-Dependent Data Stream Computations;
Peter Chapman. Syntactic Conditions for Invertibility in Sequent Calculi;
CATS 2008 Wollongong
Committee
James Harland, RMIT University, Melbourne (Co-chair);
Prabhu Manyem, University of Ballarat, Australia (Co-chair);
Argimiro Arratia, University of Valladolid, Spain;
Richard Brent, Australian National University, Canberra;
Hajo Broersma, University of Durham, UK;
Cristian Calude, University of Auckland, NZ;
Jeremy Dawson, Australian National University, Canberra;
Thomas Erlebach, University of Leicester, UK;
Graham Farr, Monash University, Melbourne;
Joachim Gudmundsson, NICTA, Sydney;
Venkatesan Guruswami, University of Washington, Seattle;
Seokhee Hong, NICTA and the University of Sydney, Sydney;
Costas Iliopoulos, Kings College, London;
Mike Johnson, Macquarie University, Sydney;
Jens Palsberg, UCLA;
David Pearce, Victoria University of Wellington, NZ;
R. Ramanujam, Institute of Mathematical Sciences, Chennai, India;
Joe Ryan, University of Ballarat, Australia;
Matthias Stallmann, North Carolina State University, USA;
Richard Taylor, Defence Science and Technology Organisation, Canberra;
Hans van Ditmarsch, University of Otago, NZ;
accepted papers
Martin Bunder. The Inhabitation Problem for Intersection Types;
Xiaowei Huang, Li Jiao and Weiming Lu. Weak Parametric Failure Equivalences and Their Congruence Formats;
Olga Ohrimenko and Peter Stuckey (student paper) Modelling for Lazy Clause Generation;
Samuel Huston, Jakob Puchinger and Peter Stuckey (student paper) The Core Concept for 0/1 Integer Programming;
Matthew Asquith, Joachim Gudmundsson and Damian Merrick (student paper) An ILP for the Line Ordering Problem;
Elena Morozova. A Multidimensional Bisection Method for Unconstrained Minimization Problem;
Nita H. Shah, Ajay S. Gor and Hui Wee. Optimal Joint Vendor-Buyer Inventory Strategy for Deteriorating Items with Salvage Value;
Marko Samer and Stefan Szeider. Tractable Cases of the Extended Global Cardinality Constraint;
Egbert Mujuni and Frances Rosamond. Parameterized Complexity of the Clique Partition Problem;
Luke Mathieson and Stefan Szeider. The Parameterized Complexity of Regular Subgraph Problems and Generalizations;
Vadim Levit and Eugen Mandrescu. Well-covered Graphs and Greedoids;
Minh Nguyen, Mirka Miller and Guillermo Pineda-Villavicencio (student paper) On the Non-existence of Even Degree Graphs with Diameter Two and Defect Two;
Yuichi Asahiro, Eiji Miyano and Hirotaka Ono. Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree;
Frank Ruskey and Aaron Williams (student paper) Generating Balanced Parentheses and Binary Trees by Prefix Shifts;
Ching-Lueh Chang, Yen-Wu Ti and Yuh-Dauh Lyuu. Testing Embeddability Between Metric Spaces;
Shi Bai and Richard P. Brent (student paper) On the Efficiency of Pollard's Rho Method for Discrete Logarithms;
Lindsay Groves. Verifying Michael and Scott's Lock-Free Queue Algorithm using Trace Reduction;
CATS 2007 Ballarat
Program committee:
Tetsuo Asano JAIST, Japan;
Otfried Cheong KAIST, Korea;
David Clarke CWI, Amsterdam;
Rowan Davies University of Wesern Australia;
Joachim Gudmundsson (Co-chair) NICTA, Australia;
Barry Jay (Co-chair) UTS, Australia;
Mike Johnson Macquarie University, Australia;
Bruce Litow James Cook University, Australia;
John Lloyd Australian National University, Australia;
Prabhu Manyem University of Ballarat, Australia;
Brendan McKay Australian National University, Australia;
David Pearce Victoria University of Wellington, New Zealand;
Kunihiko Sadakane Kyushu University, Japan;
Tasos Viglas University of Sydney, Australia;
Accepted Papers:
(4,g)-cages for $gge 5$ are tightly supconnected by Jianmin Tang, Yuqing Lin, Camino Balbuena and Mirka Miller;
Computing a Minimum-Dilation Spanning Tree is NP-hard by Otfried Cheong, Herman Haverkort and Mira Lee;
A Linear Time Algorithm for Pricing Sequential Barrier European Options by Peng Gao and Ron van der Meyden;
Probabilistic Logic under Uncertainty by Audun Josang;
Some Structural and Geometric Properties of Two-Connected Steiner Networks by Kenneth Hvam,Line Reinhardt, Pawel Winter and Martin Zachariasen;
Analysis of Busy Beaver Machines via Induction Proofs by James Harland;
Constructing Strictly Positive Families by Peter Morris, Thorsten Altenkirch and Neil Ghani;
On the Power of Structural Violations in Priority Queues by Amr Elmasry, Claus Jensen and Jirki Katajainen;
Effective Prediction and its Computational Complexity by Richard Taylor;
On The Complexity of Manipulating Elections by Tom Coleman and Vanessa Teague;
Fast Exponential-Time Algorithms for the Forest Counting in Graph Classes by Heidi Gebauer and Yoshio Okamoto;
Planning with Time Limits in BDI Agent Programming Languages by Lavindra de Silva, Anthony Dekker and James Harland;
Minimum Augmentation of Edge-Connectivity with Monotone Requirements by in Undirected Graphs Toshimasa Ishii;
Quantumly Corrupted Codewords and Quantum List Decoding by Tomoyuki Yamakami;
An efficient solution method for relaxed variants of the nesting problem by Benny Kjær Nielsen;
Constructing Optimal Highways by H.-K. Ahn, H. Alt, T. Asano, S. W. Bae, P. Brass, O. Cheong, C. Knauer, H.-S. Na, C.-S. Shin and A. Wolff;
An optimal broadcasting protocol for mobile video-on-demand by Regant Hung and Hing-Fung Ting;
Termination of Abstract Reduction Systems by Jeremy Dawson and Rajeev GoreMichiel;
CATS 2006 Hobart
Committee:
Tetsuo Asano JAIST, Japan.;
Mike Atkinson University of Otago, New Zealand.;
Ljiljana Brankovic University of Newcastle, Australia;
Prosenjit Bose Carleton University, Canada;
Rod Downey University of Wellington, New Zealand;
Joachim Gudmundsson (Co-chair) NICTA, Australia;
James Harland RMIT, Australia;
Barry Jay (Co-chair) UTS, Australia;
Mike Johnson Macquarie University, Australia;
Paul Kelly Imperial College, U.K.;
Delia Kesner Universite de Paris 7, France;
Ling Li Curtin University, Australia;
Eugenio Moggi Univ. di Genova, Italy;
Jens Palsberg UCLA, U.S.A.;
Andrew Solomon UTS, Australia;
Gerhard Woeginger Eindhoven University of Technology, The Netherlands;
Accepted Papers:
Geometric spanners with few edges and degree five, Michiel Smid;
Graph orientation algorithms to minimize the maximum outdegree, Yuichi Asahiro, Eiji Miyano, Hirotaka Ono and Kouhei Zenmyo;
Multilayer Grid Embeddings of Iterated Line Digraphs, Toru Hasunuma;
Compositional type systems for stack-based low-level languages, Ando Saabas and Tarmo Uustalu;
Mechanically Verifying Correctness of CPS Compilation, Ye Henry Tian;
Formalising the L4 microkernel API, Rafal Kolanski and Gerwin Klein;
Combinatorial Generation by Fusing Loopless Algorithms, Tadao Takaoka and Stephen Violich;
The Busy Beaver, the Placid Platypus and Other Crazy Creatures, James Harland;
A polynomial algorithm for codes based on directed graphs, Andrei Kelarev;
On the complexity of the DNA Simplified Partial Digest Problem, Jacek Blazewicz and Marta Kasprzak;
On the Approximability of Maximum and Minimum Edge Clique Partition Problems, A. Dessmark, J. Jansson, A. Lingas, E.-M. Lundell and M. Persson ;
Faster Algorithms for Finding Missing Patterns, Shuai Cheng Li;
On the logical Implication of Multivalued Dependencies with Null Values, Sebastian Link;
Boolean equation solving as graph traversal, Brian Herlihy, Peter Schachte and Harald Sondergaard;
Learnability of Term Rewrite Systems from Positive Examples, M. R. K. Krishna Rao;
On-Demand Bounded Broadcast Scheduling with Tight Deadlines, Chung Keung Poon, Yinfeng Xu and Feifeng Zheng;
Greedy algorithms for on-line set-covering and related problems, Giorgio Ausiello, Aristotelis Giannakos and Vangelis Paschos;
CATS 2005 Newcastle
Committee:
Mike Atkinson (Co-chair), University of Otago, New Zealand;
Frank Dehne (Co-chair), Griffith University, Australia;
James Harland, RMIT University, Melbourne, Australia;
Barry Jay, University of Technology, Sydney, Australia;
Mike Johnson, Macquarie University, Sydney, Australia;
David Wolfram, Infosys Australia;
Rod Downey, Victoria University of Wellington, New Zealand;
Angele Hamel, Wilfrid Laurier University, Canada;
Joerg Sack, Carleton University, Canada.;
Roy Dyckhoff, University of St Andrews, UK.;
Andrew Rau-Chaplin, Dalhousie University, Canada.;
Bakhadyr Khoussainov, University of Auckland, New Zealand.;
Bruce Litow, James Cook University.;
Rodney Topor, Griffith University.;
Andrew Solomon, University of Technology, Sydney.;
Accepted Papers:
C. McCartin, R. Downey: Bounded Persistence Pathwidth;
A. Dekker: The Symmetry Ratio of a Network;
E. Prieto: The Method of Extremal Structure on the k-Maximum Cut Problem;
B. Dongol: Concurrent Program Design in the Extended Theory of Owicki and Gries;
S. Saunders: Efficient Algorithms for Solving Shortest Paths on Nearly Acyclic Digraphs;
T. Ishil: Minimum Cost Source Location Problem with Local 3-Vertex-Connectivity Requirements;
M. Dumas: When are two Workflow Processes the Same?;
N. Danner, C. Pollett: Circuit Principles and Weak Pigeonhole Variants;
K. Trentelman: Factorising temporal specifications;
M. Lanthier: Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces;
R. Solis-Oba: On packing squares with resource augmentation: maximizing the profit;
M. Compton: Stenning's Protocol Implemented in UDP and Verified in Isabelle;
D. Hemer: Plug-in proof support for formal development environments;
H. Machi: The Relative Completeness of the First-Order CTL*;
M. Persson: Approximate Clustering of Fingerprint Vectors with Missing Values;
CATS 2004 Ottago
Committee:
Mike Atkinson (Chair), University of Otago, New Zealand.;
Colin Fidge, University of Queensland, Brisbane, Australia.;
James Harland, RMIT University, Melbourne, Australia.;
Xuemin Lin, University of New South Wales, Sydney, Australia.;
Barry Jay, University of Technology, Sydney, Australia.;
Mike Johnson, Macquarie University, Sydney, Australia.;
David Wolfram, Expert Information Services, Melbourne, Australia.;
Mike Fellows Newcastle University, Australia.;
Rod Downey, Victoria University of Wellington, New Zealand.;
Peter Gibbons, University of Auckland, New Zealand.;
Angele Hamel, Wilfrid Laurier University, Canada.;
Joerg Sack, Carleton University, Canada.;
Frank Dehne, Carleton University, Canada.;
Roy Dyckhoff, University of St Andrews, U;
Accepted Papers:
Jeremy Dawson: Formalising General Correctness ;
Taolue Chen, Jingyang Zhou, Tingting Han, Jian Lu: Checking Open Congruence in chi-Calculus ;
Greg O'Keefe: Towards a Readable Formalisation of Category Theory ;
Sebastian Link, Sven Hartmann: A Membership Algorithm for Functional and Multi-valued Dependencies in the Presence of Lists ;
Gem Stapleton, Jean Flower: Automated Theorem Proving with Spider Diagrams;
David Hemer: Higher-order associative commutative pattern matching for component retrieval ;
Hirotaka Ono, Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Toshinori Sakuma, Masafumi Yamashita : How to Collect Balls Moving in the Euclidean Plane;
William Duckworth: Small Edge Dominating Sets of Regular Graphs ;
Jesper Jansson, Charles Choy, Kunihiko Sadakane, Ken W.-K. Sung: Computing the Maximum Agreement of Phylogenetic Networks ;
Neil Leslie, Edwin Mares: CHR: A constructive relevant natural-deduction logic;
Elio Giovannetti: Type Inference for Mobile Ambients in Prolog ;
Vladimir Estivill-Castro: Generating Nearly Sorted Sequences - The use of measures of disorder;
Tak-Wah Lam, Johnny Ngan, Kar-Keung To, Prudence Wai-Ha Wong: Aggressive Online Deadline Scheduling;
Quy Tuan Nguyen, Barry Jay, H.Y. Lu: The Polymorphic Imperative: a Generic Approach to In-place Update;
Graham Farr: Cost-effectiveness of algorithms (informal presentation);
Margaret Mitchell:Creating Vertex Series Parallel Graphs from Directed Acyclic Graphs is NP-Complete (informal presentation);
Stefan Szeider:The Parameterized Complexity of SAT Backdoors (informal presentation);
CATS 2003 Adelaide
Committee
Michael Atkinson, Otago University, Dunedin, New Zealand.;
John Crossley, Monash University, Melbourne, Australia.;
XiaoTie Deng, City University of Hong Kong.;
Mike Fellows Newcastle University, Australia.;
Colin Fidge, University of Queensland, Brisbane, Australia.;
James Harland (Chair), RMIT University, Melbourne, Australia.;
Matthew Hennessy, University of Sussex, Brighton, UK;
Barry Jay, University of Technology, Sydney, Australia.;
Mike Johnson, Macquarie University, Sydney, Australia.;
Xuemin Lin, University of New South Wales, Sydney, Australia.;
David Wolfram, Expert Information Services, Melbourne, Australia.;
Accepted Papers:
Information Leakage Detection in Boundary Ambients Chiara Braghin, Agostino Cortesi, Riccardo Focardi;
A New Machine-checked Proof of Strong Normalisation for Display Logic Jeremy Dawson, Rajeev Gore;
Mobility Types for Mobile Processes in Mobile Ambients M. Coppo, M. Dezani-Ciancaglini, E. Giovannetti;
An Optimal Family of Bounded-Degree Broadcast Networks Michael Dineen, Nian Zhou;
Large 2-Independent Sets of Regular Graphs W. Duckworth, M. Zito;
On the Relative Complexity of Labelled Modal Tableaux Guido Governatori;
Minimum Augmentation of Edge-connectivity between Vertices and Sets of Vertices in Undirected Graphs Toshimasa Ishii, Yoko Akiyama, Hiroshi Nagamochi;
Flow Analytic Type System for Array Bound Checks Yutaka Matsuno, Hiroyuki Sato;
Space and Time Adaptive Non-blocking Algorithms Maurice Herlihy, Victor Luchangco, Mark Moir;
The Reverse Problem of Range Query Tadao Takaoka;
Hierarchical Automata and P-systems N. Sabadini and R. Walters;
Linearity and Passivity David Wright;
Three approaches to Partiality in the Sketch Data Model Michael Johnson, Robert Roseburgh;
Formal Semantics for Program Paths Karl Lermer, Colin Fidge, Ian Hayes;
Cutting Up is Hard to Do: the Parameterised Complexity of k-Cut and Related Problems Rodney Downey, Vladimir Estivill-Castro, Michael Fellows, Elena Prieto, Frances Rosamund;
Arbitrage in Frictional Foreign Exchange Market Mao-cheng Cai, Xiaotie Deng;
Characterizing polynomial time computable functions using theories with weak set existence principles Aleksander Ignjatovic and Phuong Nguyen;
CATS 2002 Melbourne
Committee
Asat Arslanov, Monash University, Australia.;
Hossam ElGindy, the University of New South Wales, Australia.;
James Harland (Chair), Royal Melbourne Institute of Technology, Australia.;
Mike Johnson, Macquarie University, Australia.;
Mathai Joseph, Tata R&D, India.;
Barry Jay, University of Technology, Sydney, Australia.;
Ron van der Meyden, the University of New South Wales, Australia.;
Harald Sondergaard, Melbourne University, Australia.;
Lim Soon Wong , Kent Ridge Digital Labs, Singapore.;
Michael Winikoff , Royal Melbourne Institute of Technology, Australia.;
David Wood, Sydney University, Australia.;
Accepted papers:
A Category-Theoretic Approach to Social Network Analysis Anthony Dekker;
Typed Behavioural Equivalences for Processes in the Presence of Subtyping Matthew Hennessy, Julian Rathke;
Drawing Ruled Surfaces Using the Dual De Boor Algorithm Rena Ding, Ian Parkin;
Towards an Arithmetic Theory of Consistency Enforcement based on the Preservation of \delta-Constraints Sebastian Link, Klaus-Dieter Schewe;
Dedekind completion as a method for constructing new Scott domains Klaus Grue;
On the Structure of Counterexamples to Symmetric Orderings for BDDs Rakesh Verma, Sarah Hwang;
Bisimulation-based Non-deterministic Admissible Interference with Applications to the Analysis of Cryptographic Protocols John Mullins, Stephane Lafrance;
Efficient Algorithms for Maximum Subarray Problem by Distance Matrix Multiplication Tadao Takaoka;
Computing over K-modules Neil Ghani, Anne Heyworth;
Zooming out on Higraph-based Diagrams: Syntactic and Semantic Issues Stuart Anderson, John Power, Konstantinos Tourlas;
Don't Care Non-determinism in Logic Program Refinement David Hemer, Ian Hayes, Paul Strooper, Robert Colvin;
Sketch Data Models, Relational Schema and Data Specifications Michael Johnson, Robert Rosebrugh;
