GLL parse-tree generation

Backtracking techniques which are often used to extend recursive descent (RD) parsers can have explosive run-times and cannot deal with grammars with left recursion. GLL parsers are fully general, worst-case cubic parsers which have the recursive descent-like property that they are easy to write and to use for grammar debugging. They have the direct relationship with the grammar that an RD parser has. In this paper we give an algorithm for generating GLL parsers which build an SPPF representation of the derivations of the input, complementing our existing GLL recognition algorithm, and we show that such parsers and recognisers are worst-case cubic.     

SoundRiver: Semantically‐Rich Sound Illustration

Sound is an integral part of most movies and videos. In many situations, viewers of a video are unable to hear the sound track, for example, when watching it in a fast forward mode, viewing it by hearing‐impaired viewers or when the plot is given as a storyboard. In this paper, we present an automated visualization solution to such problems. The system first detects the common components (such as music, speech, rain, explosions, and so on) from a sound track, then maps them to a collection of programmable visual metaphors, and generates a composite visualization. This form of sound visualization, which is referred to as SoundRiver, can be also used to augment various forms of video abstraction and annotated key frames and to enhance graphical user interfaces for video handling software. The SoundRiver conveys more semantic information to the viewer than traditional graphical representations of sound illustration, such as phonoautographs, spectrograms or artistic audiovisual animations.     

Reusable abstractions for modeling languages

Model-driven engineering proposes the use of models to describe the relevant aspects of the system to be built and synthesize the final application from them. Models are normally described using Domain-Specific Modeling Languages (DSMLs), which provide primitives and constructs of the domain. Still, the increasing complexity of systems has raised the need for abstraction techniques able to produce simpler versions of the models while retaining some properties of interest. The problem is that developing such abstractions for each DSML from scratch is time and resource consuming.     

Teaching Java backwards

Teaching programming concepts in a more object-oriented way is a growing trend in Computer Science education. This paper takes the idea of abstraction-first teaching a step further, by using Bloom’s Taxonomy to design a course to present factual content early, followed by higher-level cognitive skills. In the course described here, factual content was covered rapidly, then reinforced by assignments, laboratory sessions and tutorials, aimed at building higher cognitive skills. The resulting course was successful in relatively rapidly bringing a class doing a “bridging” diploma up to the level required for dealing with a second-year course. As compared with previous runs of the diploma where much more time was spent in preparation for advanced courses, the class using the new approach performed better, suggesting that the approach used is worthy of further study.     

Iterative algorithms for discrete periodic Riccati matrix equations

In this paper, two iterative algorithms are constructed to obtain the positive definite solutions of the discrete periodic algebraic Riccati matrix equations. In these two algorithms, the estimation of the unknown matrices are updated by using the available estimation information at the current iteration step. The convergence properties of the proposed algorithms are also given. Finally, numerical examples are employed to illustrate the effectiveness of the proposed algorithms.     

An undecidable property of context-free linear orders

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.     

网络日志中周期模式的挖掘

提出了一种新的对时序数据库周期模式的挖掘方法,即将数据库中要分析的某一个属性列首先进行信号化,信号化后的数据可以应用信号分析领域的处理方法对其进行分析和挖掘。利用小波变换多分辨率分析的方法对信号化后网络日志数据库中的数据在不同的时间尺度上进行分析和挖掘,从中提取出单位时间内网络受到攻击次数的时间周期规律。     

Equality sets of prefix morphisms and regular star languages

We consider equality sets of prefix morphisms, that is, sets E(g₁,g₂)={w|g₁(w)=g₂(w)}, where g₁ and g₂ are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form πA(E(g₁,g₂)) for some prefix morphisms g₁ and g₂, and a projection πA which deletes the letters not in A.     

A parametric periodic Lyapunov equation with application in semi-global stabilization of discrete-time periodic systems subject to actuator saturation

This paper is concerned with semi-global stabilization of discrete-time linear periodic systems subject to actuator saturation. Provided that the open loop characteristic multipliers are within the closed unit circle, a low gain feedback design approach is proposed to solve the problem by state feedback. Our approach is based on the solution to a parametric discrete-time periodic Lyapunov equation. The proposed approaches not only generalize the corresponding results for time-invariant systems to periodic systems, but also reveal some important intrinsic properties of this class of periodic matrix equations. A numerical example is worked out to illustrate the effectiveness of the proposed approaches.