Some Limits of Language: A Perspective from Formal Grammars and Languages by Prof Arvind Joshi, School of Engineering and Applied Science, University of Pennsylvania, USA

Limits of language can be studied from various perspectives such as morphology, syntax, and semantics, among others. At the syntactic level, one direction that has been pursued very actively is via the theory of formal languages, beginning with the so-called Chomsky hierarchy. In this hierarchy, the finite state languages (regular languages) and the context free languages (CFL) have been studied very extensively, leading to many important results relevant to syntax as well as parsing. At the same time, inadequacy of these two classes of grammars (languages) for capturing natural languages has been well documented by now.
A careful look at the pumping lemma for context free languages led to the discovery of the so-called tree adjoining grammars (TAG) and to the notion of mildly context sensitive languages (MCSL), which has served as a framework for showing equivalences among other systems (such as Combinatory Categorial Grammars, CCG and Head Grammars (HG), for example). This has led to a deeper understanding of the limits of language, more specifically, by trying to provide an answer to the question: how far do we need to be beyond CFL to achieve syntactic adequacy.
I will try to describe some of this recent work by a number of researchers in the past few years.

Aravind Joshi did his undergraduate work in India and his graduate work at the University of Pennsylvania in Electrical Engineering, while simultaneously attending some courses in Linguistics at the same University. Since 1961 he has been a faculty member in the Department of Computer and Information Science and the Department of Linguistics. At present, he is a Professor of Computer and Cognitive Science and a Member of the Institute for Research in Cognitive Science.
Besides working on some problems in the mathematics of language, at present, he is involved in a project on discourse annotation, jointly with Bonnie Webber (Edinburgh U.) and Rashmi Prasad (U. Wisconsin), for creating the Penn Discourse Treebank (PDTB).

Event details

  • When: 15th October 2013 14:00 - 15:00
  • Where: Purdie Theatre C
  • Series: School Seminar Series
  • Format: Seminar

St Andrews Students – Experience with Industrial Internships

Internships are fantastic opportunities to gain some practical experience as well as find out what is happening the real world of computer science! Come and hear some our UG students share their experiences of their 2013 summer internships.
Melissa Mozifian: Adobe
Waqas Arshad: AIG
Mariya Hristova: Google STEP
Sam Koch: Facebook

Event details

  • When: 1st October 2013 14:00 - 15:00
  • Where: Purdie Theatre C
  • Series: School Seminar Series
  • Format: Seminar

Scaling Skyscanner’s Flight Search & Making Mobile Applications at Skyscanner

Welcome to the first presentation in the School of Computer Science’s Seminar Series.

Please join us on for a seminar on Skyscanner’s technology this Tuesday (September 24) at 14:00 in Purdie Lecture Theatre C.

The two talks combined will take about 50 minutes with time for questions, and combine two topics presented by Skyscanner experts:

Grzegorz Janas- Project Manager Mobile Applications
Simon Thorogood- Senior Architect Development Engineering
Scott Krueger- Technical Manager Databases
Skyscanner: http://www.skyscanner.net/

Abstract:
Come and hear from Skyscanner Engineers on the Challenges behind engineering the world’s fastest growing Metasearch product and our journey towards being the “most trusted online travel company in the world” Skyscanner has 24 million unique monthly visitors and 25 million installed apps generating one-third of its traffic through mobile.

Everybody welcome.

Event details

  • When: 24th September 2013 14:00 - 15:30
  • Where: Purdie Theatre C
  • Series: School Seminar Series
  • Format: Seminar

Constraint Modelling Winners

Medal given to prize winning team
At the annual conference on Constraint Programming, CP 2013, Ian Gent and Ian Miguel were members of the winning team in the “First International Lightning Model and Solve” competition. Many thanks to the organisers of the event and especially to Allen van Gelder of UCSC for having the idea of entering a manual team and for inviting us to join in.

This was a quick event – just two hours – and the team’s strategy was to solve problems by hand, using pen and paper.  This was reflected in their team name, “Mano”.

Ian Gent has written a much longer blog post about the experience, why the team won, and why it is not bad news for constraint programming.

 

Creator of the World Wide Web Honoured

Professor Alan Dearle from the School of Computer Science, and Dean of Science at the University, has the honour of acting as Laureator for Sir Tim Berners-Lee today, one of the international scholars and thinkers awarded an Honorary Degree as part of the University’s 600th Anniversary celebrations.

Join Professor Dearle and Sir Tim Berners-Lee and watch the Honorary Graduation Live on the University website.

Computer Science Orientation Week 2013

After a welcome talk by Head of School Steve Linton, orientation 2013 is underway in the School. Monday and Tuesday offered various overviews, module talks and academic briefings. Anyone who missed these events will find related material on the School Homepage.

School President James Anderson represented the School at Academic Fayre. Student activity was observed in the honours lab and that’s before the official start of semester. We are particularly pleased to welcome the first intake of Gateway students.

orientation

A Gaming afternoon for first year students proved popular on Wednesday with Halo, Fifa and Lego Star Wars in operation. An undergraduate pizza fest followed later in the afternoon with an excellent turn out demonstrating the friendly supportive nature of our returning cohort. It’s great to see them back for another year of hard work.

gamefest1

pizzatime

The student experience is paramount here in the school, so we take this opportunity to thank our recent graduates for the NSS 2013 results, where they rated individual subjects for student satisfaction. St Andrews was number one in the UK for Computer Science. We aim to keep it that way.

PhD Reading Party 2013

The 2013 PhD Reading Party was held last month at the Burn House, just outside Edzell in the North East of Scotland.

It was an opportunity for research students to give a talk in a relaxed atmosphere, about their research interests. It also allowed for some socialising while wandering through the nearby woods and rivers.
burn1
Each student gave a 5 minute talk with time for questions and discussions. Additionally, to encourage them to make the presentation of their research industry-friendly, a pitching competition was set up. The top three were: Shantanu Pal, Dean Phoomikiattisak and Shyam Reyal. The whole academic part of the trip was rounded off by a talk by Tom Kelsey on ‘Academic Careers’.

burn2
In the free time some went off to explore the nearby forest and salmon rich river while others decided to play football or volleyball, enjoy the quiet surroundings or build the highest Jenga tower at the Burn, so far.

Text and Images courtesy of Ruth Hoffmann, Jamie Carson and Shyam Reyal.

Dr Adam Barker Awarded Royal Society Fellowship

Dr Adam Barker has been awarded a prestigious Royal Society Industry Fellowship. The scheme aims to enhance knowledge transfer in science and technology in the UK, and provides an outstanding opportunity to demonstrate the benefits of how industry and academia can work effectively together to drive innovation.

Adam will be spending 50% of his time for two years on a collaborative project at Cloudsoft in TechCube, a world-class startup space in Edinburgh. Adam will be working on multi-cloud application management with Dr Alex Heneveld, Co-Founder and Chief Technology Officer (CTO) and his team. He will be contributing towards Brooklyn – an open-source, policy-driven control plane for distributed applications, and the OASIS Cloud Application Management for Platforms (CAMP) standard.