Associate Professor

Department Computer Science

National University of Ireland, Cork

Cork

Ireland

Email: mpcsATcs.ucc.ie

UCC Campus Office Phone: (+353) (21) 4903083 (UCC)

Main phone: (+353) (21) 4322104 (CEOL, Airport Business Park)

Directions to my office on UCC campus.

Directions to CEOL can be found on the Center for Efficiency-Oriented Languages webpage.

PhD Carnegie Mellon University. University College Cork (UCC).

Director of SFI-funded Center for Efficiency Oriented Languages (CEOL).

Project Leader, BCRI Project: Semantics/Quantitative Domain Theory.

SFI Industrial collaboration with Sun Labs, RTSJ group

2006-Present

Associate Professor, Department of Computer Science, University College Cork (UCC).

2000-2006

Senior Lecturer, Department of Computer Science,
University College Cork (UCC).

1998-2000

Lecturer, Department of Computer Science,
University College Cork (UCC).

1997-1998

Post Doc, University of Siegen, TCS group.

1996-1997

Marie Curie Fellow, EUROFOCS Project, Imperial College London

Theory and Formal Methods
Section of the Department of
Computing

Follow this link for more information
on UCC and the National University of Ireland.

Follow this link for the webopedia online dictionary for computer and
Internet technology definitions.

Editorial panel: Information Sciences.

Webpage of the association: MCFA.

Journal Applied General
Topology.

See Topology Atlas for a list
of related journals.

Editorial area:
Topology and Computer Science.

Marie Curie Fellowship,
EUROFOCS Award, Imperial College, 1996.

DAAD Scholarship for Faculty,
German Academic Exchange Service, Schloss Dagstuhl, 2001. DAAD Alumni

Science Foundation
Ireland Investigator Award, 2003.

Science Foundation
Ireland Investigator Industrial Collaboration Award", 2004.

Collaboration with RTSJ group, Dr. Greg Bollella, Distinguished
Engineer, Sun Labs Europe.

Domains
IV Workshop in Bonn, October 2-4, 1998.

MFCSIT2000, First Irish Conference on the Mathematical
Foundations of Computer Science and Information Technology, National
University of Ireland, Cork, 20th and 21st July, 2000.

MFCSIT2000 drew 71 participants, including many Irish participants and
a majority of attendants from other European countries and the US.

MFCSIT2002, Second Irish Conference on the Mathematical Foundations of
Computer Science and Information Technology, National University of
Ireland, Galway, 18-19 July, 2002.

MFCSIT2004,
Third Irish Conference on the Mathematical Foundations of
Computer Science and Information Technology, Trinity College Dublin,
22-23 July, 2004.

Project: Semantics of Programming Languages: Quantitative Domain Theory.

Maria O'Keeffe (PhD) and one Post Doc

Science Foundation Ireland

SFI Investigator Award.

Director of Center for Efficiency
Oriented Languages (CEOL).

Applications for EMBARC PhD and EMBARC Post Doc positions. Please refer to the CEOL webpage for further information.

** Improved Software Timing. **

My interests in exploring this general area include Automated
Average-Case Analysis (Analysis of Algorithms) and its intersections
with

- Real-Time Languages (Semantics)
- Software Engineering
- Software-Hardware Co-Design
- Processor Design/Embedded Systems.

The CEOL centre, funded
by Science Foundation Ireland, currently develops MOQA (MOdular
Quantitative Analysis) a novel programming language conductive to
improved average-case timing and the associated Timing Tool,
Distri-Track, which goes considerably beyond the state of the art in
Average-time analysis.

** Former research directions: **

- Complexity spaces and their applications.
- Quantitative domain theory.
- Generalized metrics, quasi-uniform spaces, non Hausdorff spaces
and their applications

to Computer Science.

- Sun Labs
- POP, Carnegie Mellon University
- LFCS, University of Edinburgh
- PPS group, Paris VII
- Topology and Applications, Polytechnical University of Valencia
- University of Birmingham
- Oxford University
- TCS, University of Siegen
- Department of Computing, Imperial College London
- University of Capetown, ...

Dr. Marc van Dongen (affiliated member)

Dr. John Herbert

Dr. Joseph Manning

Prof. Michel Schellekens

Graduate Students:

Michaela Heyer (Graduated, MSc, 2005)

Maria O'Keeffe, PhD student

David Hickey, PhD student

Christophe Gosset, PhD student

Jacinta Townley, PhD student

James McEnry, PhD student

Post Docs:

Dr. Thierry Vallee

Dr. Menouer Boubekeur

Dr. Homeira Pajoohesh (2003-2005, Currently at CUNY)

Industrial Placement Students/UREKA students/Research
Assistants/Summer Internships:

Anthony O'Mahoney (former Industrial Placement, 2003)

David Devlin (former UREKA, current Industrial Placement, 2005-2007)

Diarmuid Early (former UREKA, current Research Assistant,2005-2007)

Raja Banka (UREKA, 2006)

Chandra Sekhar (Summer Internship, 2006)

Co-editor, Volume 40 of Electronic Notes of Theoretical Computer
Science, Elsevier. Editors: T. Hurley , M. Mac an Airchinnigh ,
M. Schellekens and A. Seda (coordinating editor)

Coordinating editor, special volume of the journal Applied Categorical
Structures, Kluwer related to the conference MFCSIT2000. Editors: M. Schellekens, A. K. Seda, D. Spreen.

The Marie Curie Fellowship Association: MCFA.

Boole Centre for Research in Informatics (BCRI), UCC.

Currently leading project in Semantics of Programming Languages and Quantitative Domain Theory.

Invited Workshop Speaker, joint workshop SFI-NSFC (National Science Foundation China), Beijing, June 12-16, 2006.

MFCSIT06, Cork, Ireland.

*Complexity Spaces:
Lifting and Directedness*

*Topology Proceedings* 22, 403 - 425, 1999.

*Quasi-metric properties of Complexity Spaces*, joint with
S. Romaguera

*Topology and its Applications* 98, 311-322,
1999.

*Cauchy filters and strong completeness of quasi-uniform spaces*,
joint with S. Romaguera

*Rostock. Math. Kolloq.* 54, 2000.

*The quasi-metric of complexity convergence*, joint with
S. Romaguera

*Questiones Mathematicae* 23, 359-374, 2000.

*On the Yoneda completion of a quasi-metric space*, joint with
H. P. Kuenzi

*Theoretical Computer Science*, Volume 276 (1-2) of April 2002.

*The
correspondence between partial metrics and semivaluations*

*Theoretical Computer Science* 315, 135-149, 2004.

*Extendible
spaces*

* Applied General Topology*, accepted for
publication, to appear in vol 3, no. 2, November 2002.

R. Bresin, B. Di Martino, S. Kroener and M. Schellekens. Editorial
introduction of the Information Science Panel

*Annals of the Marie
Curie Fellowship Association* 1, 2000.

*Duality and quasi-normability for complexity spaces*, joint with
S. Romaguera

* Applied General Topology*, vol 3, nr. 1, 2002.

*A characterization of partial metrizability. Domains are
quantifiable*

*Theoretical Computer Science* 305, 409 - 432, 2003.

*Partial metric monoids and semivaluation spaces. *

Joint with S. Romaguera, Topology and its Applications, accepted for publication, to appear.

*The relationship between balance and the speed of algorithms*,

wiht M. O'Keeffe and H. Pajoohesh, Hadronic Journal, accepted for
publication, to appear in Vol. 28, 2005.

*Binary trees equiped with semivaluations*, with
H. Pajoohesh.

* Decision trees of algorithms and a semivaluation to measure
their distance*, with M. O'Keeffe, H. Pajoohesh.

* Compositionality: a Real-Time Paradigm to facilitate WCET and ACET
timing *, with D. Hickey.

Electronic Notes in Theoretical Computer Science, Volume 1, Proc. 11th Conf. on the Mathematical Foundations of Programming Semantics, Elsevier, 1995, 211-232.

*On
upper weightable spaces*

Papers on General Topology and
Applications, 11th Summer Conf., University of Southern Maine, Annals
of the New York Academy of Science 806, New York Academy of Science,
New York, 1996, 348-363.

*Complexity Spaces
Revisited*

Proceedings Prague Topology
Symposium, Topology Atlas 1997, 337-348.

*Valuations
Revisited*

Proceedings 3rd Irish Workshop on Formal
Methods (IWFM'99), Electronic Workshops in
Computing, British Computer Science Society, 1999, 1 - 8.

*A note on completeness of the complexity space*, joint with
S. Romaguera

Seminarberichte Fach. Math. FernUniv. Hagen 66, 1999, 99-105.

*The ideal completion is not sequentially adequate*, joint with
H. P. Kuenzi

Proceedings of the workshop Domains IV, Rolandseck, Electronic Notes of
Theoretical Computer Science, Volume 35, Elsevier, 2000.

*Weightable quasi-metric semigroups and
semilattices*, joint with S. Romaguera

Proceedings of
MFCSIT2000, Volume 40 of Electronic Notes of
Theoretical Computer Science, Elsevier, 2003.

*Weightable Directed Spaces: Partial Metrics = Generalized
(E)valuations*

Dagstuhl Seminar Report 209, Editors: S. Brookes,
M. Droste, M. Mislove, 1999. Seminar on Domain Theory and its Applications, Schloss Dagstuhl.

*Norm-weightable Riesz spaces and the dual complexity space*

Joint with M. O'Keeffe and S. Romaguera, ENTCS volume 74, Elsevier,
Proceedings MFCSIT2002, 17 pages, 2003.

*The average merge time: an intuitive interpretation. *

Joint with M. O'Keeffe, ENTCS volume 74, Elsevier, Proceedings
MFCSIT2002, 12 pages, 2003.

*Quantitative
Domain Theory*, ERCIM News No.50, July 2002

* ``Solving Recurrence Relations using Generating Functions''*, joint with A. A. Uskova, M. Van Dongen, Proceedings of The Annual Scientific
Meeting of Moscow Engineering Physics Institute, Thesis for Scientific
Conference MEPhI - 2004, Volume 2, Software and Informational Technologies, MEPhI press, 2004, p. 95-96.

*Partial metric monoids and semivaluation spaces. *

Joint with S. Romaguera, Electronic Notes in Theoretical Computer Science, Elsevier,
accepted for publication, to appear.

* SLIDES - Iberoamerican Conference, Murcia, 2003. *

CS3010 Algorithms and automata

For information on postgraduate studies, visit our online handbook.

Some usefull links: ContentsDirect from Elsevier Science (automatic mailing of contents of Elsevier
journals).

Access to the worldwide topology community can be had through
the Topology Atlas.

`mpcsATcs.ucc.ie`

Phone: 4322104

Here are the directions to my office on Western Road. You need to make a prior appointment by email, since I am heading a research centre at the Cork Airport Business Park (www.ceol.ucc.ie)

My interests for the final year projects are the following:

I) ONLINE TEACHING

I like to improve teaching methods and come up with new ways to present material, especially visual ways to teach algorithms.

- ALGORITHMS: If you followed CS3010 with me, you'll know I present insertion sort in a "visual way", explaining how the algorithm proceeds by inserting a given element in a priorly sorted list. This computation idea can be displayed online and in an interactive way. Look at my project on "Interactive course design" if you are interested in contributing to visualizing material this way. I put the course CS1010 (on Logic) online and intend to do the same with CS3010 (on Algorithms) in an interactive way. Here's your chance to contribute to such an experiment. A second aspect of the project is to implement a query system, where students are asked questions on the material and can provide online answers which then are complemented with feedback.

- SORTING NETWORKS: A related project is the one on Sorting Networks.

II) BOARD GAMES (SOLITAIRE)

I have a side interest in board games, so I included one of them in the final year projects: Solitaire. The game has been around for a long time (since the 18th century). Apparently it was invented by a French prisoner during his stay in the Bastille (though this probably is a myth). Leibniz was an avid player of the game.

To get some feel for the game, try the frog jumping version which needs some time to load.

The game can be purchased in some toy stores or airport shops. One shop in Cork which supplies the game is J. Joyce on Princes Street (a board version and a drawn version in the "Klutz" book on board games). You can also opt to build the game by drawing the grid and using flat pebbles or checkers pieces. It is useful to have a version to carry out the project, for instance in the case of a heuristics oriented project. A model is available in my office, so you'll know what to look for. I have a smaller version you can borrow (all pegs need to be returned!). This demo game will be passed on to various students taking the project, so it is best you obtain your own.

I chose the game for its apparent simplicity. The game is extremely easy to understand. There is only "one" rule of play for the English version (which has a cross shaped board and allows for vertical or horizontal jumps of pegs over another peg) and "two" rules for the French version (which has four extra holes for the pegs and allows for vertical or horizontal jumps AND diagonal jumps of pegs over another peg).

Despite this simplicity, a search for solutions can quickly become "GYNORMOUS" in scope (we can discuss some known search space results to give you an idea).

But don't despair: there are several references of different computer science approaches which will put you well on your way to experiment with this. See the "TIPS" and references below for some approaches which you could follow.

BOARD SHAPE OF SOLITAIRE:

- the French board.

RULES FOR SOLITAIRE:

For English solitaire:

You can jump a peg, say peg 1, over another peg, say peg 2, which is adjacent to peg1, provided peg 2 lands in an empty hole on the other side of peg 2, adjacent to peg 2 again. The peg which has been jumped, i.e. peg 2, is then removed. Moves can be carried out horizontally (from left to right or the converse) or vertically (either downwards or upwards).

For French solitaire:

Diagonal moves of the above nature (peg-over-peg) are also allowed in addition to the vertical and horizontal moves. This is necessary since one can show that without diagonal moves, the French version has no solution starting with an empty hole in the middle and ending up with a single peg in the center.

PROJECTS

- FRENCH SOLITAIRE (test your "search design skills"): This project will nicely test your skills for implementing searches for solutions to a given problem. This project would be good for one student, but I am open to discuss other approaches if there is more interest.

- ENGLISH SOLITAIRE (test your "heuristic development skills"): This project regards what is now regarded as traditional solitaire and is generally referred to as English solitaire. I worked out some derived rules for the game in order to speed up the search. These heuristics need testing and possibly you can come up with more rules. There is some literature onthis as well, so there is plenty of scope to play around. Interested? Have a look at the project ...

- GENERAL SOLITAIRE (test your "user friendly design skills"): This project requests the implementation of solitaire (both the French and the English version), where you can view online step by step solutions to existing problems, halt the computation, backtrack, and continue with your own version of the solution. Or indeed, start an entirely new solution approach of your own. You can push the limits by incoporating e.g. triangular solitaire or one dimensional solitaire as well.

TIPS: If you have an interest in e.g. GENETIC ALGORITHMS or specialized SEARCH TECHNIQUES, there are some references to papers (see online references below) which provide various search techniques and approaches in these areas. More projects could be done, improving on these approaches.

Each of these has the potential to lead to a very good project and a research report could be produced in case we/you push the boundaries of what is know a bit further. (Of course that is not a requirement, but one of the ways to reach an excellent result).

If you have an interest in mathematics, that too can be catered for, since there are some simple approaches in GROUP THEORY as well. If you like puzzles, why not design your own version of the game? For instance by changing the board shape or the rules and study this in any of the above ways. I am open to new suggestions pending mutual agreement.

Have a look at triangle solitaire and one dimensional solitaire for some alternative versions. Or also: unconstrained solitaire (cf. references).

REFERENCES FOR SOLITAIRE PROJECTS:

Some online references to get you started:

- On Heuristics

- On Search space (Dutch, but I will be glad to translate)

- On Group Theory

- And finally, George Bell's webpage on solitaire for recent progress in the area.

Books available from our library:

These are somewhat mathematical in nature, but useful to gather some ideas on possible versions of the game, heuristics and history.

- "The ins and out of peg solitaire", John D. Beasley, Oxford U.P., 1985.

- "Winning ways for your mathematical plays", Elwyn R. Berlecamp, John H. Conway, Richard K. Guy Imprint London : Academic Press, 1982.

III) FOUNDATIONS OF COMPUTING.

- THEORETICAL PROJECT: My main research area is in foundations of computing. This year I listed a project on Worst-Case Execution Time, Sorting Networks and Timing Analysis.

I presented one theory problem on merging some time ago, and two students took it, both very successfully (one actually led to a research paper later on). So if you are interested in theory, don't be shy.

IV) YOUR OWN IDEA: If you have your own idea and think it would link up in some way with my own interests, feel free to sound me out.

I prefer to be contacted by Email, so that will be your first move.