CATS 1998: Perth, WA, Australia

Xuemin Lin (Ed.): Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS'98), Perth, WA, Australia, February 2-3, 1998. Australian Computer Science Communications 20(3) Springer-Verlag Singapore Pte. Ltd. 1998

Keynote Address

Ming Li, Paul M. B. Vitányi: Average-Case Analysis Using Kolgomorov Complexity (Abstract). 1-4

Keynote Address

Takeshi Tokuyama: Application of Algorithm Theory to Data Mining. 5-20

Session 1

Toru Hasunuma, Hiroshi Nagamochi: Independent Spanning Trees with Small Depths in Iterated Line Digraphs. 21-36
Weifa Liang, George Havas: Finding the k Most Vital Edges with Respect to Minimum Spanning Trees for k=2 and 3. 37-50
Chang-Biau Yang, Tung-Hsing Liu: Wormhole Routing on the Star Graph Interconnection Network. 51-66
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Anna Östlin: Inferring Ordered Trees from Local Constraints. 67-76

Session 2

Tadao Takaoka: A New Measure of Disorder in Sorting - Entropy. 77-86
Jyrki Katajainen: The Ultimate Heapsort. 87-96
Frank Albers, Peter Damaschke: Delayed Correction - Binary Search with Errors Made Very Simple but Efficient. 97-106

Session 3

Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting: Default-Sensitive PreProcessings for Finding Maxima. 107-120
Steve Callaghan, Gerard Ellis, James Harland: Filters for Graph Matching. 121-136
Ying Teh Tsai, Chuan Yi Tang: An Average Case Analysis of the Branching Algorithm for Solving $k$-Satisfiability Problems. 137-150

Session 4

John Maraist: Separating Weakening and Contraction in a Linear Lambda Calculus. 151-166
Ernie Ong: Optimisation Nets. 167-182
Yukiyoshi Kameyama, Masahiko Sato: A Classical Catch/Throw Calculus with Tag Abstractions and its Strong Normalizability. 183-198

Session 5

Brian Murphy, Richard P. Brent: On Quadratic Polynomials for the Number Field Sieve. 199-214
David R. Powell, Lloyd Allison, Trevor I. Dix, David L. Dowe: Alignment of Low Information Sequences. 215-230
L. Yohanes Stefanus, Ronald N. Goldman: On the Linear Independence of the Bivariate Discrete Convolution Blending Functions. 231-244

Session 6

Alessandra Di Pierro, Herbert Wiklicky: A Banach Space Based Semantics for Probabilistic Concurrent Constraint Programming. 245-260
A. J. Field, Peter G. Harrison, K. Kanani: Automatic Generation of Verifiable Cache Coherence Simulation Models from High-Level Specifications. 261-276
Cristian S. Calude, Marjo Lipponen: Computational Complementarity and Sofic Shifts. 277-290
A. Pgourtzis, K. Sharma, E. Zachos: Tree Models and Probabilistic Polynomial Time Computations. 291-304