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 BibTeX

Keynote Address

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

Keynote Address

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

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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