Marking student programs using graph similarity

We present a novel approach to the automated marking of student programming assignments. Our technique quantifies the structural similarity between unmarked student submissions and marked solutions, and is the basis by which we assign marks. This is accomplished through an efficient novel graph similarity measure (AssignSim). Our experiments show good correlation of assigned marks with that of a human marker.     

Evaluating the usability of natural language query languages and interfaces to Semantic Web knowledge bases

The need to make the contents of the Semantic Web accessible to end-users becomes increasingly pressing as the amount of information stored in ontology-based knowledge bases steadily increases. Natural language interfaces (NLIs) provide a familiar and convenient means of query access to Semantic Web data for casual end-users. While several studies have shown that NLIs can achieve high retrieval performance as well as domain independence, this paper focuses on usability and investigates if NLIs and natural language query languages are useful from an end-user's point of view. To that end, we introduce four interfaces each allowing a different query language and present a usability study benchmarking these interfaces. The results of the study reveal a clear preference for full natural language query sentences with a limited set of sentence beginnings over keywords or formal query languages. NLIs to ontology-based knowledge bases can, therefore, be considered to be useful for casual or occasional end-users. As such, the overarching contribution is one step towards the theoretical vision of the Semantic Web becoming reality.     

Decidability of operation problems for T0L languages and subclasses

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.     

The organization of interaction design pattern languages alongside the design process

This work explores the possibility of taking the structural characteristics of approaches to interaction design as a basis for the organization of interaction design patterns. The Universal Model of the User Interface (Baxley, 2003) is seen as well suited to this; however, in order to cover the full range of interaction design patterns the model had to be extended slightly. Four existing collections of interaction design patterns have been selected for an analysis in which the patterns have been mapped onto the extended model. The conclusion from this analysis is that the use of the model supports the process of building a pattern language, because it is predictive and helps to complete the language. If several pattern writers were to adopt the model, a new level of synergy could be attained among these pattern efforts. A concluding vision would be that patterns could be transferred freely between pattern collections to make them as complete as possible.     

Common knowledge does not have the Beth property

Common knowledge is an essential notion for coordination among agents. We show that the logic of common knowledge does not have the Beth property and thus it also lacks interpolation. The proof we present is a variant of Maksimova's proof that temporal logics with ‘the next’ do not have the Beth property. Our result also provides an explanation why it is so difficult to find ‘nice’ deductive systems for common knowledge.     

Unary finite automata vs. arithmetic progressions

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.     

An Optimizing Compiler for Parallel Chemistry Simulations

Well designed domain specific languages have three important benefits: (1) the easy expression of problems, (2) the application of domain specific optimizations (including parallelization), and (3) dramatic improvements in productivity for their users. In this paper we describe a compiler and parallel runtime system for modeling the complex kinetics of rubber vulcanization and olefin polymerization that achieves all of these goals. The compiler allows the development of a system of ordinary differential equations describing a complex vulcanization reaction or single-site olefin polymerization reaction—a task that used to require months—to be done in hours. A specialized common sub-expression elimination and other algebraic optimizations sufficiently simplify the complex machine generated code to allow it to be compiled—eliminating all but 8.0% of the operations in our largest program and enabling over 60 times faster execution on our largest benchmark codes. The parallel runtime and dynamic load balancing scheme enables fast simulations of the model.     

Cameo: an alternative model of concurrency for Eiffel

We present a new concurrency model for the Eiffel programming language. The model is motivated by describing a number of semantic problems with the leading concurrency model for Eiffel, namely SCOOP. Our alternative model aims to preserve the existing behaviour of sequential programs and libraries wherever possible. Comparison with the SCOOP model is made. The concurrency aspects of the alternative model are presented in CSP along with a model of exceptions. The results show that while the new model provides increased parallelism, this comes with the price of increased overhead due to lock management.