Disciplined,efficient, generalised folds for nested datatypes

Nested (or non-uniform, or non-regular) datatypes have recursive definitions in which the type parameter changes. Their folds are restricted in power due to type constraints. Bird and Paterson introduced generalised folds for extra power, but at the cost of a loss of efficiency: folds may take more than linear time to evaluate. Hinze introduced efficient generalised folds to counter this inefficiency, but did so in a pragmatic way: he did not provide categorical or equivalent underpinnings, so did not get the associated universal properties for manipulating folds. We combine the efficiency of Hinzes construction with the powerful reasoning tools of Bird and Patersons.Correspondence and offprint request to: Clare Martin, orgdivisionSchool of Computing and Mathematical Sciences, Wheatley Campus, Oxford Brookes University, Oxford OX33 1HX, UK.Received April 2002 Accepted in revised form May 2003 by R.C. Backhouse     

Adjoint folds and unfolds—An extended study

Folds and unfolds are at the heart of the algebra of programming. They allow the cognoscenti to derive and manipulate programs rigorously and effectively. However, most, if not all, programs require some tweaking to be given the form of an (un)fold. In this article, we remedy the situation by introducing adjoint (un)folds. We demonstrate that most programs are already of the required form and thus are directly amenable to formal manipulation. Central to the development is the categorical notion of an adjunction, which links adjoint (un)folds to standard (un)folds. We discuss a multitude of basic adjunctions and ways of combining adjunctions and show that they are directly relevant to programming. Furthermore, we develop the calculational properties of adjoint (un)folds, providing several fusion laws, which codify basic optimisation principles. We give a novel proof of type fusion based on adjoint folds and discuss several applications—type fusion states conditions for fusing a left adjoint with an initial algebra to form another initial algebra. The formal development is complemented by a series of examples in Haskell.     

Two extensions of topological feedback entropy

Topological feedback entropy (TFE) measures the intrinsic rate at which a continuous, fully observed, deterministic control system generates information for controlled set-invariance. In this paper we generalise this notion in two directions; one is to continuous, partially observed systems, and the other is to discontinuous, fully observed systems. In each case, we show that the corresponding generalised TFE coincides with the smallest feedback bit rate that allows a form of controlled invariance to be achieved.     

A two-level generative model for cloth representation and shape from shading

In this paper, we present a two-level generative model for representing the images and surface depth maps of drapery and clothes. The upper level consists of a number of folds which will generate the high contrast (ridge) areas with a dictionary of shading primitives (for 2D images) and fold primitives (for 3D depth maps). These primitives are represented in parametric forms and are learned in a supervised learning phase using 3D surfaces of clothes acquired through photometric stereo. The lower level consists of the remaining flat areas which fill between the folds with a smoothness prior (Markov random field). We show that the classical ill-posed problem-shape from shading (SFS) can be much improved by this two-level model for its reduced dimensionality and incorporation of middle-level visual knowledge, i.e., the dictionary of primitives. Given an input image, we first infer the folds and compute a sketch graph using a sketch pursuit algorithm as in the primal sketch (Guo et al., 2003). The 3D folds are estimated by parameter fitting using the fold dictionary and they form the "skeleton" of the drapery/cloth surfaces. Then, the lower level is computed by conventional SFS method using the fold areas as boundary conditions. The two levels interact at the final stage by optimizing a joint Bayesian posterior probability on the depth map. We show a number of experiments which demonstrate more robust results in comparison with state-of-the-art work. In a broader scope, our representation can be viewed as a two-level inhomogeneous MRF model which is applicable to general shape-from-X problems. Our study is an attempt to revisit Marr's idea (Marr and Freeman, 1982) of computing the 2frac12D sketch from primal sketch. In a companion paper (Barbu and Zhu, 2005), we study shape from stereo based on a similar two-level generative sketch representation.     

The impulse analysis of the T-S fuzzy singular system via Kronecker index

The problem of impulse analysis is considered for the T-S fuzzy singular system by using the Kronecker index and the generalised Kronecker index in this paper. The T-S singular system is divided into two cases: the uniformly regular T-S fuzzy singular system and the non-uniformly regular T-S fuzzy singular system. The contribution of this paper is twofold. First, a new definition of the generalised Kronecker form is introduced, and the algorithm of finding the generalised Kronecker form is given. Second, two theorems are proved, one is that the uniformly regular T-S fuzzy singular system is impulsive if and only if the Kronecker index is greater than one, the other one is the non-uniformly regular T-S fuzzy singular system is impulsive if and only if the generalised Kronecker index is greater than one. Finally, two numerical simulations and the population model with stage structure are carried out to show the consistency with theoretical analysis and illustrate the effectiveness of the algorithm.     

病理嗓音发声系统的非对称建模研究

为了在病理嗓音识别中为特征参数选择提供依据,提出声带非对称力学建模仿真病变声带并进行分析研究。依据声带的分层结构和组织特性,建立声带力学模型,耦合声门气流,求取模型输出的声门源激励波形。采用遗传粒子群 拟牛顿结合优化算法(Genetic particle swarm optimization based on quasi-Newton method, GPSO-QN)将模 型输出的声门源和实际目标声门波相匹配,提取优化模型参数。仿真实验结果表明,该声带模 型能产生与实际声门源相一致的声门波形,同时也证明了左右声带生理组织间的非对称性是产生病理嗓音的重要原因。     

Algebraic–coalgebraic specification in CoCasl

We introduce CoCasl as a light-weight but expressive coalgebraic extension of the algebraic specification language Casl. CoCasl allows the nested combination of algebraic datatypes and coalgebraic process types. Moreover, it provides syntactic sugar for an observer-indexed modal logic that allows e.g. expressing fairness properties. This logic includes a generic definition of modal operators for observers with structured equational result types. We prove existence of final models for specifications in a format that allows the use of equationally specified initial datatypes as observations, as well as modal axioms. The use of CoCasl is illustrated by specifications of the process algebras CSP and CCS.     

Asymptotic behaviours and stability of zero dynamics in nonlinear discrete-time systems using Taylor approach and multirate input

It is well known that the existence of unstable sampled zero dynamics is recognised as a major barrier in many control problems. When the usual digital control with zero-order hold (ZOH) or fractional-order hold (FROH) input is used, unstable sampled zero dynamics inevitably appear in the discrete-time model even though the continuous-time system with relative degree more than or equal to three is of minimum phase. In this paper, we show how an approximate sampled-data model can be obtained for nonlinear systems by the use of multirate input and hold such as a generalised sample hold function (GSHF) in order that discrete zero dynamics of the resulting model can be arbitrarily placed. Furthermore, the properties of sampled zero dynamics are studied and the conditions for ensuring the stability of sampling zero dynamics of the desired model are derived. The results presented here generalise well-known notion of sampling zero dynamics from the linear case to nonlinear systems, and GSHF can provide some advantages over ZOH or FROH in terms of stability of discrete system zero dynamics.     

nSPARQL: A navigational language for RDF

Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In this paper, we propose the query language nSPARQL that uses nested regular expressions to navigate RDF data. We study some of the fundamental properties of nSPARQL and nested regular expressions concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly traversing the input graph. We also show that nesting is necessary in nSPARQL to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators. Regarding complexity of evaluation, we prove that given an RDF graph G and a nested regular expression E, this problem can be solved in time O(|G||E|).     

Containment and disjointedness in partitioned normal form relations

Containment and disjointedness are two important properties in the updating materialized views. Disjointedness means that the set of tuples to be inserted in the view are disjoint from the view, and containment means that the tuples to be deleted from the view are contained in the view. In this paper we consider how to extend the definition of containment and disjointedness from flat relations to nested relations which are in partitioned normal form. The two correctness requirements that we place on our definitions are that they must be faithful and precise; where faithful means that the definition should coincide with the corresponding definition for flat relations when the nested relations are flat, and precise means that the definition should coincide with the corresponding definition for flat relations after performing a total unnest on the nested relation. We then propose definitions for disjointedness and containment for partitioned normal form relations and prove that the definitions proposed are faithful and precise. We also show that simple set based extensions of the definitions for flat relations are not correct since they are not precise. Received: 9 October 2000 / 17 September 2001