C.S. Calude, M.J. Dinneen, S. Sburlan (eds.). Combinatorics, Computability, Logic, Proceedings of DMTCS'01, Springer-Verlag, London, July 2001, XI + 250 pages softcover, ISBN.

The third Discrete Mathematics and Theoretical Computer Science conference (DMTCS'01) has been organised for the first time outside New Zealand at the Faculty of Mathematics and Computer Science, "Ovidius" University, Constanta with the co-operation of the Maritime Academy "Mircea cel Batran", Constanta. It was held held in the beautiful Romanian city of Constanta on the Black Sea.

The conference was dedicated to Professor Frank Harary on the occasion of his 80th Birthday.

Frank Harary

Frank holds the PhD from the University of California at Berkeley, 1948. Prior to his doctorate he worked as a meteorologist, an aeronautical engineer, and an instructor of physics at Princeton University, Brooklyn College, City College of New York and New York University. During his doctoral studies in Berkeley, he was a ballroom dance instructor.

He spent two years at the Institute for Advanced Study in Princeton, was a research mathematician at Bell Telephone Laboratories, a visiting assistant professor of mathematics at Princeton University, and had fellowships at Cambridge University (Churchill College) and Oxford University (Wolfson College). He had multiple visiting positions at universities on all continents.

In 1955, at the University of Michigan, he created the first courses on combinatorial theory and on graph theory in the world. He founded both the Journal of Combinatorial Theory (1966) and the Journal of Graph Theory (1977). He is a member of the editorial board of 16 scholarly journals.

Frank has published over 700 papers, mainly on graph theory and its applications, not only in mathematics and computer science, but also in anthropology, art, biology, linguistics, physics, chemistry, electrical engineering, geography, psychology.

Frank has written 8 books and edited 10 others. His 1969 book, Graph Theory, became the fifth most cited work in the mathematical research literature during 1978-79. His latest, Graph Theory and Geography will be published by Wiley as an electronic book in May 2001.

Frank has delivered over one thousand invited lectures at conferences and universities in 77 countries, the two most recent being Uruguay (Montevideo, August 2000) and Zimbabwe (Harare, November 2000).

Frank has Erdös number 1, having written two papers with the most prolific mathematician of our times.

Not an academic honor, but a rather unusual form of recognition, occurred when the successful film "Good Will Hunting" displayed formulas and graphs he had published in a paper on the enumeration of trees. In the film, these formulas were supposed to show a fiendishly difficult unsolved mathematical problem which the star, Matt Damons, solved effortlessly!


Table of Contents

Invited papers

Frank Harary
Early Computer Science Adventures of a Mathematician

Hajime Ishihara
Sequentially Continuity in Constructive Mathematics

Piergiorgio Odifreddi
Recursive Functions: An Archeological Look

Ioan Tomescu
The Number of Graphs and Digraphs with a Fixed Diameter and Connectivity


Contributed papers

Hatem M. Bahig, Mohamed H. El-Zahar and Ken Nakamula
Some Results for Some Conjectures in Addition Chains

Verónica Becher, Sergio Daicz and Gregory Chaitin
A Highly Random Number

Douglas S. Bridges
Dini's Theorem: A Constructive Case Study

Henning Fernau
Even Linear Simple Matrix Languages: Formal Language Aspects

George Georgescu and Afrodita Iorgulescu
Pseudo-BCK Algebras: An Extension of BCK Algebras

Lane A. Hemaspaandra and Harald Hempel
P-Immune Sets with Holes Lack Self-Reducibility Properties

Daniel Hort and Jirí Rach23unek
Lex Ideals of Generalized MV-Algebras

Jouni Järvinen
Armstrong Systems on Ordered Sets

Vadim E. Levit and Eugen Mandrescu
Unicycle Bipartite Graphs with Only Uniquely Restricted Maximum Matchings

Martin Plátek, Tomás Holan and Vladislav Kubon
On Relax-ability of Word-Order by D-grammars

Adriana Popovici and Dan Popovici
On the Structure of Linear Cellular Automata

Robert Rettinger, Xizhong Zheng Romain Gengler, and Burchard von Braunmühl
Monotonically Computable Real Numbers

Peter Schuster, Luminita Vîta and Douglas S. Bridges
Apartness as a Relation Between Subsets

Ludwig Staiger
How Large is the Set of Disjunctive Sequences?

Vincent Vajnovszki
A Loopless Generation of Bitstrings without p Consecutive Ones

Vitaly Voloshin
Greedy Algorithms for the Lower and Upper Chromatic Numbers