CDMTCS: 1995 ANNUAL REPORT
 Directors Professor D. S. Bridges (Waikato) and Professor
C. S. Calude (Auckland)
 AURC Representative on Management Committee Not nominated.
 Participating members
The CDMTCS includes the following faculty members:
P. Bonnington (Mathematics, Tamaki),
D. S. Bridges (Mathematics, Waikato),
C. Calude (Computer Science, Auckland),
J. Cleary, (Computer Science, Waikato),
M. D. E. Conder (Mathematics, Auckland),
R. W. Doran (Computer Science, Auckland),
A. G. French (Mathematics, Waikato),
J. Gibbons (Computer Science, Auckland),
P. Gibbons (Computer Science, Auckland),
H. Guesgen (Computer Science, Auckland),
P. R. Hafner (Mathematics, Auckland),
F. Kroon (Philosophy, Auckland),
M. Lennon (Computer Science, Tamaki),
I. Melchert (Mathematics, Waikato),
S. Reeves (Computer Science, Waikato),
M.R. Titchener (Computer Science, Tamaki),
I. H. Witten (Computer Science, Waikato).

International Board The following distinguished experts are serving
on the CDMTCS
International
Advisory Board:
M. Arslanov,
R. C. Backhouse,
J. Casti,
G. J. Chaitin,
C. J. Colbourn,
E. W. Dijkstra,
J. H. Dinitz,
J. A. Goguen,
R. L. Graham,
J. Hartmanis,
H. Jürgensen,
C. C. Lindner,
R. Mathon,
B. D. McKay,
A. Nerode,
G. Rozenberg,
A. Salomaa,
J. Seberry,
D. van Dalen.
 Aim
The Centre, which is a joint venture involving the Computer Science and
Mathematics Departments of the Universities of Auckland and Waikato, was
founded in 1995 to support basic research on the interface between
mathematics and computing, to increase local knowledge in these areas, and
to broaden research skills in New Zealand.
The aim of the Centre's Management Committee is to build one of the world's
best centres in Discrete Mathematics and Theoretical Computer Science,
comparable to those of the most important similar centres in North America
and Europe. By doing so, the Committee hopes to foster research and
development in these areas within the South Pacific region, and to create
links between researchers in that region and their counterparts in the rest
of the world.
 Research Matters
The research aims of the Centre are in the following broad areas:

Artificial Intelligence: theoretical aspects of artificial
intelligence; formal concepts of artificial intelligence; efficient
algorithms for solving complex AI problems like scheduling, planning,
constraint satisfaction, etc.
 Combinatorial Optimization:
computational techniques for the efficient construction and analysis of
many optimal types of combinatorial configurations (including graphs,
codes and designs), using deterministic methods exploiting symmetries and
algebraic properties, and, when deterministic methods become infeasible,
probabilistic methods such as simulated annealing, hillclimbing, and
genetic programming.
 Computability and Complexity:
computability and noncomputability in pure mathematics (in particular,
functional analysis and operator theory), theoretical physics
(specifically, quantum mechanics), theoretical economics, and other
areas; complexity of computation in those fields. Algorithmic information
theory.
 Constructive Algorithmics: methods for calculating programs from
their specifications,
and the design of notations for such calculation; also, the
investigation of software support for the calculational
process.
 Research Grants
 M.
Apperley, J. Grundy, S. Reeves and J. Venable,
FoRST Grant $ 360,000 (over 3 years),
 S. Reeves, UWRC Grant, $ 10,500 (over 2 years),
 C.S. Calude, AURC Grant, $ 5,000
 M.D.E. Conder, AURC Grant, $ 1,000
 M.D.E. Conder, Marsden Fund Award, $ 84,000 (over 3 years)
 M.D.E. Conder, Claude McCarthy Fellowship, $ 5,000
 H. Guesgen, AURC Grant, $1,008

I. Witten et al. NZ Lottery Grants Board, $ 20,000

I. Witten et al., FoRST Grant, $192,000 (over 5 years)

R. Nicolescu & M.R. Titchener, AURC Grant, $ 13,000
 M.R. Titchener, AURC Grant, $ 2,500
 M.R. Titchener & Ulrich Guenther, AURC Grad Fund, $ 2,700
 Educational Activities
The Centre has supported the following undergraduate and graduate courses:
 0654.418/518 Foundations of Mathematics (taught by A.G. French and D.S. Bridges)

26.225 Discrete Mathematics (taught by Paul Bonnington and John Pearson)
 26.315 Logic (taught by Maths and Philosophy Departments)
 26.325 Combinatorial Structures (taught by Margaret Morton)
 07.350 Mathematical Foundations of Computer Science (taught by Cristian Calude and Fred Kroon),
 26.416 Algebraic Combinatorics (taught by Marston Conder)
 07.755 Algorithmic Information Theory (taught by Cristian Calude)
 07.320 Algorithmics (taught by Peter Gibbons and Cristian Calude)
 07.750 Program Derivation (taught by Jeremy Gibbons)
 07.720 Advanced Design and Analysis of Algorithms (taught by Peter Gibbons)
 07.457 Data Structures (taught by Ioan Tomescu,
Bucharest University, CDMTCS visitor),
 07.458 Computation Theoretic Aspects of Cellular Automata (taught
by Sheng Yu,
University of Western Ontario, CDMTCS visitor),
 07.765 Advanced Artificial
Intelligence (taught by Hans Guesgen)

0654.317 Discrete Mathematics & Theoretical Computer Science (taught by D.S Bridges,
A.G. French, K.A. Broughan and I.
Melchert)

0654.240 Mathematical Foundations of Computer Science (taught by G. French and I. Melchert)
 0657.416A Topics in Artificial Intelligence (taught by I. Witten)
 415.742 Data Communications (taught by Peter Fenwick and M.R. Titchener)
The following graduate students are
working in close connection with the research program of the Centre:

Asat Arslanov (PhD student, ``Theoretical Computer Science"),

Elena Calude (PhD student, ``Theoretical Aspects of Artificial Intelligence"),

Peter Dobcsanyi (PhD student, ``Combinatorial Computation using Distributed Processing"),

Matt Humphrey (PhD student, ``Humancomputer Interaction Using Relational Algebra"),

Stuart Inglis (PhD student, ``Textual Image Processing"),
 James Webb: (PhD student,
``Computational Techniques for Solving Chessboard Problems"),

S. Irvine (PhD student),

John Pearson (PhD student, ``Studies in Combinatorics and Group Theory"),

Cameron Walker (PhD student, ``Compact Presentations for the Symmetric Groups"),

Michael Wang (PhD student, ``Constructive Aspects of the Dirichlet Problem"),

Craig NevillManning (PhD student, ``Programming by Example"),

Tony Smith (PhD student, ``Probabilitybased Grammar Induction"),

Ulrich Guenther (PhD student, ``Robust Image Compression Coding''),
Wang Yuchuan (PhD student,
``Constructive aspects of the Dirichlet Problem"),
 Robyn Curtis (Masters student, ``The Cycle Double Cover Problem")

Samantha Stephenson (Masters student, ``Sharply Transitive Sets and
Finite Projective Planes"),

Brent Martin (Masters student, ``Instancebased Learning: Nearest Neighbour with
Generalisation"),

James Littin (Masters student, ``Learning Rules with Interattribute Dependencies").
 Visitors
Prof. Helmut Jürgensen (University Western Ontario, Canada),
Prof. Ioan Tomescu (Bucharest University, Romania),
A/Prof. Sheng Yu (University Western Ontario, Canada),
Prof. Tudor Zamfirescu (Dortmund University, Germany),
Dr Mike Newman (Australian National University),
Dr Eamonn O'Brien (Australian National University),
Prof Cheryl Praeger (Univerity of Western Australia).
 Financial Statement The Centre has been started only for half a year,
so there has been no financial activity for 1995.
 Publications and Technical Reports

C. P. Bonnington,
C. H. C. Little, Foundations of Topological Graph Theory,
SpringerVerlag, 1995.

C. P. Bonnington, W. Imrich and N. Seifter, Geodesics in transitive graphs,
J. Combin. Theory Ser. B, 1995.

C. P. Bonnington, D. Archdeacon and J. Siran,
A Nebeskytype characteristation for relative maximum genus,
Technical Report 329, Dept. of Math., The Uni. of Auckland, 1995.

C. P. Bonnington, W. Imrich and M. Watkins,
Separating double rays in locally infinite planar graphs, Discrete
Math., 145:6172, 1995.
 D. S. Bridges and G. B. Mehta. Representations of Preference Orderings, Lecture Notes in
Economics and Mathematical Systems 422, SpringerVerlag, Berlin, 1995.
 D. S. Bridges.
Constructive mathematics and unbounded operatorsA reply to Hellman, J. Phil.
Logic 24 (1995), 549561.

C. Calude. What is a random string? J. UCS, Vol. 1,1 (1995), 4866.

C.Calude, M.Zimand. Effective category and measure in abstract complexity
theoryextended abstract, Proceedings FCT'95, Lectures Notes in Computer
Science 965, SpringerVerlag, Berlin, 1995, 156171.

C.Calude. What is a random string?Extended Abstract, in
W.DepauliSchimanovich,
E.Koehler, F.Stadler (eds.).
The Foundational Debate, Complexity and Constructivity
in Mathematics and Physics,
Kluwer, Dordrecht,1995, 101113.

C.Calude, D.I.Campbell, K.Svozil, D.Stefanescu.
Strong determinism vs. computability, in W.DepauliSchimanovich,
E.Koehler, F.Stadler (eds.).
The Foundational Debate, Complexity and Constructivity
in Mathematics and Physics,
Kluwer, Dordrecht,1995, 115131.

G.J.Chaitin, A.Arslanov, C.Calude. Programsize complexity computes the halting
problem, EATCS Bull, 57 (1995), 198200.

M.D.E. Conder, Twoelement generation of the finite reflection groups,
Quarterly Journal of Mathematics (Oxford) Ser.2
46 (1995), 95106.

M.D.E. Conder & Jianbei An,
The Alperin and Dade conjectures for the simple Mathieu groups,
Commmunications in Algebra 23 (1995), 27972823.

M.D.E. Conder & M.J. Morton,
Classification of trivalent symmetric graphs of small order,
Australasian Journal of Combinatorics 11 (1995), 139149.

M.D.E. Conder & B.J. Everitt,
Regular maps on nonorientable surfaces,
Geometriae Dedicata 56 (1995), 209219.

M.D.E. Conder, P.J. Lorimer & C.E. Praeger)
Constructions for arctransitive digraphs,
Journal of the Australian Mathematical Society 59 (1995), 6180.

M.D.E. Conder & Jianbei An,
On the numbers of 2weights, unipotent conjugacy classes, and irreducible
Brauer 2characters of finite classical groups,
Proceedings of the American Mathematical Society 123 (1995),
22972304.

M.D.E. Conder, Semiautomated theorem proving: the impact of computers
on pure mathematics research, in: Innovative Use of Technology in
Teaching and Research in Mathematics (Proceedings of the First Asian
Conference on Technology in Mathematics, Singapore, December 1995),
pp. 18.
 Gibbons, J. `An InitialAlgebra Approach to Directed Acyclic Graphs'. LNCS
947: Third International Conference on the Mathematics of Program
Construction, Kloster Irsee, July 1995, ed Bernhard Moeller,
SpringerVerlag, 282303.

Gibbons, J. `Dotted and Dashed Lines in Metafont'. Proceedings
of the TeX Users' Group Annual Meeting, ed Robin Fairbairns, St
Petersburg Beach, Florida, July 1995.

Gibbons, J. `Heyit Works!'. TeX and TUG News, 4(1), 1995,
49.

Gibbons, J. `Heyit Works!'. TeX and TUG News, 4(2), 1995,
36.

Gibbons, J. `Heyit Works!'. TeX and TUG News, 4(3), 1995.

Gibbons, P.B. and Mathon, R., Signings of group divisible designs and
projective planes, Australasian Journal of Combinatorics 11 (1995),
79  104.

H.W. Guesgen and J. Hertzberg.
Spatial persistence,
Applied Intelligence (Special Issue
on Spatial and Temporal Reasoning), 1995.

H.W. Guesgen.
On linguistic variables and fuzzy sets for hybrid spatial reasoning.
In Proc. IJCAI95 Workshop on Fuzzy Logic in Artificial Intelligence,
pages 19, Montréal, Canada, 1995.

H.W. Guesgen.
Integrating qualitative and quantitative spatial reasoning.
In Proc. IJCAI95 Workshop on Spatial and Temporal Reasoning, pages
8794, Montréal, Canada, 1995.

R. Weissschnur, J. Hertzberg, and H.W. Guesgen.
Experiences in solving constraint relaxation networks with Boltzmann
machines.
In Proc. CP95 Workshop on OverConstrained Systems, pages 103109,
Cassis, France, 1995.

H.W. Guesgen and A. Philpott.
Heuristics for solving fuzzy constraint satisfaction problems.
In Proc. ANNES95, pages 132135, Dunedin, New Zealand, 1995.

H.W. Guesgen.
Attacking the complexity of fuzzy constraint satisfaction problems.
In Proc. FLAMOC96, pages 6672, Sydney, Australia, 1996.

Reeves, S. (1995) Computer support for students' work in a formal system:
MacPICT, International Journal on Mathematical Education in Science and
Technology, vol. 26, no. 2, pp.159175.

Reeves, S., Goldson, D., Fung, P., O'Shea, T., Hopkins, M. and Bornat, R.
(1995) The Calculator Project  Formal Reasoning about Programs, in
Proceedings of SRIGET'94, IEEE Computer Society Press, pp.166173.

Reeves, S. and Cranefield, S. (eds.) (1995) Proceedings of the Second New
Zealand Computer Science Research Students' Conference, Department of
Computer Science, University of Waikato, Hamilton, New Zealand.

Reeves, S. (1995) Better Software in the Future?, New Zealand Journal of
Computing, volume 6, number 1A, pp. 5358.

Reeves, S. (1995) A Teaching and Support Tool for Building Formal Models of
Graphical UserInterfaces , Working paper 95/21, Department of Computer
Science, University of Waikato, August 1995.

Conklin, D. and Witten, I.H. (1995) Multiple viewpoint systems for music
prediction, J New Music Research, 24 (1) 5173, March.

Thimbleby, H., Witten, I.H., and Pullinger, D. (1995)
Concepts of
cooperation in artificial life, IEEE Trans Systems, Man and Cybernetics, 25
(7) 11661171, July.

McQueen, R.J., Garner, S.R., NevillManning, C.G., and Witten, I.H. (1995)
Applying machine learning to agricultural data, J Computing and
Electronics in Agriculture, 12 (4) 275293.

Bell, T.C., Moffat, A., Witten, I.H., and Zobel, J. (1995) The MG
retrieval system: compressing for space and speed, Communications of the
Association for Computing Machinery, 38 (4) 4142, April.

Smith, T.C. and Witten, I.H. (1995) Probabilitydriven lexical
classification: a corpusbased approach, Pacific Association for
Computational Linguistics Conference, 271283, Brisbane, Australia, April.

Witten, I.H., Cunningham, S.J., Vallabh, M., and Bell, T.C. (1995) A New
Zealand digital library for computer science research, Proc Digital
Libraries '95, 2530, Austin, Texas, June.

Bell, T.C., Bensemann, G., and Witten, I.H. (1995) Computer Science
Unplugged: Capturing the interest of the uninterested, Proc NZ Computer
Conference, Wellington, New Zealand, August.

Garner, S.R., Holmes, G., McQueen, R.J., and Witten, I.H. (1995) Machine
learning from agricultural databases: practice and experience, Proc NZ
Computer Conference, Wellington, New Zealand, August.

NevillManning, C.G., Holmes, G., and Witten, I.H. (1995) The development
of Holte's 1R classifier, Proc ANNES'95, 239242, Dunedin, New Zealand,
November.

Inglis, S. and Witten, I.H. (1995) Document zone classification using
machine learning, Proc Digital Image Computing: Techniques and
Applications, Brisbane, Australia, December.

Cleary, J.G., Teahan, W.J., and Witten, I.H. (1995) Unbounded length
contexts for PPM, in Proc Data Compression Conference, edited by J.A.
Storer and M. Cohn, pp 5261. IEEE Press, Los Alamitos, CA.

Moffat, A., Neal, R., and Witten, I.H. (1995) Arithmetic coding revisited,
in Proc Data Compression Conference, edited by J.A. Storer and M. Cohn, pp
202211. IEEE Press, Los Alamitos, CA.

Smith, T.C. and Witten, I.H. (1995) A genetic algorithm for the induction
of natural language grammars, Proc IJCAI95 Workshop on New Approaches to
Learning for Natural Language Processing, 1724, Montreal, Canada.

Witten, I.H., Moffat, A., and Bell, T.C. (1995) Compression and fulltext
indexing for digital libraries, Advances in digital libraries, edited by
N.R. Adam, B. Bhargava, and Y. Yesha, pp 181203. Springer Verlag (Lecture
Notes in Computer Science series), February.

Witten, I.H. (1995) PBD systems: when will they ever learn? PBD Workshop,
ML'95, 19, Tahoe City, CA, July.

Greenberg, S., Darragh, J.J., Maulsby, D.L., and Witten, I.H. (1995)
Predictive interfaces: what will they think of next? Extraordinary
humancomputer interaction: interfaces for users with disabilities, edited
by A.D.N. Edwards, pp 103140. Cambridge University Press, Cambridge, UK.

Moffat, A., Bell, T.C., and Witten, I.H. (1995) Lossless compression for
text and images, Int J HighSpeed Electronics, (special issue on Signal
Compression). Also published as Chapter of Signal Compression, edited by
N.S. Jayant, Work Scientific, Singapore.

Inglis, S. and Witten, I.H. (1995) Eyeing up the magic eye, NZ Science
Monthly, 6 (4) 67, May.

Maulsby, D. and Witten, I.H. (1995) Learning to describe data in actions,
Proc Workshop on Programming by Demonstration, ML'95, 6573, Tahoe City,
CA, July.

NevillManning, C.G. and Witten, I.H. (1995) Detecting sequential
structure, Proc Workshop on Programming by Demonstration, ML'95, 4956,
Tahoe City, CA, July.

Garner, S.R., Cunningham, S.J., Holmes, G., NevillManning, C.G., and
Witten, I.H. (1995) Applying a machine learning workbench: experience with
agricultural databases, Proc Workshop on Applications of Machine Learning,
ML'95, 1421, Tahoe City, CA, July; Also available as Working Paper 95/13,
Department of Computer Science, University of Waikato.
 M. R. Titchener, ``Tcode set size reference tables'',
Tamaki TCode Project Series, Nov. 1995.
 M. R. Titchener and S. Wackrow ``TCODE software
documentation'', Tamaki TCode Project Series, Oct. 1995.
 U. Günther and M. R. Titchener, ``Calculating the expected
synchronization delay for TCode sets'', Tamaki TCode Project
Series Vol. 1, No. 7, Oct. 1995, submitted IEE Pt F,
Communications in Oct. 1995.
 M. R. Titchener, ``Generalized Tcodes: an extended construction
algorithm for self synchronizing codes'', Tamaki TCode Project
Series, Sept 1995, submitted IEE Pt F, Communications, Sept. 1995.
 U. Günther, R. Nicolescu, M. R. Titchener, ``Even Tcode sets'',
Tamaki Report Series, No. 10, Sept. 1995.