Thesis Defense Friday, 31 October at 2 pm in Johnson 102: Parallel Communicating Grammar Systems with Context-Free Components Are Really Turing Complete

Open MSc thesis defense by Mary Sarah Ruth Wilkin. All are welcome.

Parallel Communicating Grammar Systems (PCGS) were introduced as a language-theoretic treatment of concurrent systems. A PCGS extends the concept of a grammar to a structure that consists of several grammars working in parallel, communicating with each other, and so contributing to the generation of strings.

PCGS are generally more powerful than a single grammar of the same type. PCGS with context-free components (CF-PCGS) in particular were shown to be Turing complete. However, this result holds only when a non-standard mean of communication (which we call broadcast communication) is used. We expand the original construction that showed Turing completeness so that broadcast communication is eliminated at the expense of introducing a significant number of additional, helper component grammars. We thus show that CF-PCGS in their original definition are indeed Turing complete. We introduce in the process several techniques that may be usable in other constructions and may be capable of eliminating broadcast communication in general.

We also show how an earlier result proving that CF-PCGS only generate context-sensitive languages is incorrect. We discover that this proof relies of coverability trees for CF-PCGS, but that such coverability trees do not contain enough information to support the proof. We are also able to conclude that coverability trees are not really useful in any pursuit other than the one already considered in the paper that introduces them (namely, determining the decidability of certain decision problems over PCGS).

2014 Research Week Poster Competition - First Prize Winner

Introducing "Neurotransmitters" to a Neural Network for Modular Concept Learning and More Accurate Classification by Tegan Maharaj (MSc candidate, Computer Science) won the first prize in the poster competition of 2014 Bishop's Research Week.

Tegan also won 2nd prize in the Bishop's Idol competition, also held during Research Week.

Undergraduate Capstone Open Source Projects

If you are interested in getting real experience building a substantial software system as part of a distributed team, you'll be interested in UCOSP!

UCOSP is a senior undergraduate course, which has been running since September 2008. In this course, teams of students from several schools work together on an open-source software project. Each student registers in the appropriate course at his or her home institution (in our case this course would be either CS 404 or CS 408) and works in tandem with their peers from across the country. During one intensive weekend early in the course, students travel to meet face-to-face and work together.

This course exposes students to the tools, working practices, and issues that are now routine in global software development. Just as importantly, it enables them to get to know their peers from across the country. UCOSP is sponsored by Canadian CS Department Chairs and several industrial partners.

If you are interested in being involved, please contact Dr. Stefan D Bruda, who is the faculty partner for UCOSP at Bishop's.