The Relevance of Semantic Subtyping

We compare Meyer and Routley's minimal relevant logic B₊ with the recent semantics-based approach to subtyping introduced by Frisch, Castagna and Benzaken in the definition of a type system with intersection and union. We show that – for the functional core of the system – such notion of subtyping, which is defined in purely set-theoretical terms, coincides with the relevant entailment of the logic B₊.     

Discrete fractional Fourier transform based on the eigenvectors of tridiagonal and nearly tridiagonal matrices

The recent emergence of the discrete fractional Fourier transform (DFRFT) has caused a revived interest in the eigenanalysis of the discrete Fourier transform (DFT) matrix F with the objective of generating orthonormal Hermite–Gaussian-like eigenvectors. The Grünbaum tridiagonal matrix T—which commutes with matrix F—has only one repeated eigenvalue with multiplicity two and simple remaining eigenvalues. A detailed eigendecomposition of matrix T is performed with the objective of deriving two orthonormal eigenvectors—common to both the F and T matrices—pertaining to the repeated eigenvalue of T. The nearly tridiagonal matrix S first introduced by Dickinson and Steiglitz and later studied by Candan et al.—which commutes with matrix F—is rigorously proved to reduce to a 2×2 block diagonal form by means of a similarity transformation defined in terms of an involutary matrix P. Moreover explicit expressions are derived for the elements of the two tridiagonal submatrices forming the two diagonal blocks in order to circumvent the need for performing two matrix multiplications. Although matrix T has the merit of being tridiagonal and does not need the tridiagonalization step as matrix S, the simulation results show that the eigenvectors of matrix S better approximate samples of the Hermite–Gaussian functions than those of matrix T and moreover they have a shorter computation time due to the block diagonalization result. Consequently they can serve as a better basis for developing the DFRFT.     

The Better Bubbling Lemma

BCD [Barendregt, Henk, Mario Coppo and Mariangiola Dezani-Ciancaglini, A filter lambda model and the completeness of type assignment, JSL 48 (1983), 931–940] relies for its modeling of λ calculus in intersection type filters on a key theorem which I call BL (for the Bubbling Lemma, following someone). This lemma has been extended in [Castagna, Giuseppe, and Alain Frisch. A gentle introduction to semantic subtyping. In PPDP05, ACM Press (full version) and ICALP05, LNCS volume 3580, Springer-Verlag (summary), 2005. Joint ICALP-PPDP keynote talk; Dezani-Ciancaglini, M., A. Frisch, E. Giovannetti and Y. Motohama, 2002. The Relevance of Semantic Subtyping, Electronic Notes in Theoretical Computer Science 70 No. 1, 15pp] to encompass Boolean structure, including specifically union types; this extended lemma I call BBL (the Better Bubbling Lemma). There are resonances, explored in [Dezani-Ciancaglini, M., R.K. Meyer and Y. Motohama, The semantics of entailment omega, NDJFL 43 (2002), 129–145] and [Dezani-Ciancaglini, M., A. Frisch, E. Giovannetti and Y. Motohama, 2002. The Relevance of Semantic Subtyping, Electronic Notes in Theoretical Computer Science 70 No. 1, 15pp], between intersection and union type theories and the already existing minimal positive relevant logic B+ of [Routley, Richard, and Robert K. Meyer, The semantics of entailment III, JPL 1 (1972), 192–208]. (Indeed [Pal, Koushik, and Robert K. Meyer. 2005. Basic relevant theories for combinators at levels I and II, AJL 3, http://www.philosophy.unimelb.edu.au/2005/2003_2.pdf, 19 pages] applies BL and BBL to get further results linking combinators to relevant theories and propositions.) On these resonances the filters of algebra become the theories of logic. The semantics of [Meyer, Robert K., Yoko Motohama and Viviana Bono, Truth translations of relevant logics, in B. Brown and F. Lepage, eds., “Truth and Probability: Essays in Honour of Hugues Leblanc,” pages 59–84, College Publications, King's College, London, 2005] yields here a new and short proof of BBL, which takes account of full Boolean structure by encompassing not only B+ but also its conservative Boolean extension CB [Routley, Richard, and Robert K. Meyer, The semantics of entailment III, JPL 1 (1972), 192–208; Meyer, Robert K., 1995. Types and the Boolean system CB+, cslab.anu.edu.au/ftp/techreports/SRS/1995/TR-SRS-5-95/meyer.ps.gz; Meyer, Robert K., Yoko Motohama and Viviana Bono, Truth translations of relevant logics, in B. Brown and F. Lepage, eds., “Truth and Probability: Essays in Honour of Hugues Leblanc,” pages 59–84, College Publications, King's College, London, 2005.].     

Explicit Substitutions à la de Bruijn: the local and global way

Kamareddine and Nederpelt[9], resp. Kamareddine and Ríos [11] gave two calculi of explicit of substitutions highly influenced by de Bruijn's notation of the λ-calculus. These calculi added to the explosive pool of work on explicit substitution in the past 15 years. As far as we know, calculi of explicit substitutions: a) are unable to handle local substitutions, and b) have answered (positively or negatively) the question of the termination of the underlying calculus of substitutions. The exception to a) is the calculus of [9] where substitution is handled both locally and globally. However, the calculus of [9] does not satisfy properties like confluence and termination. The exception to b) is the λs_e-calculus of [11] for which termination of the s_e-calculus, the underlying calculus of substitutions, remains unsolved. This paper has two aims:

(i) To provide a calculus à la de Bruijn which deals with local substitution and whose underlying calculus of substitutions is terminating and confluent.

(ii) To pose the problem of the termination of the substitution calculus of [11] in the hope that it can generate interest as a termination problem which at least for curiosity, needs to be settled. The answer here can go either way. On the one hand, although the λσ-calculus [1] does not preserve termination, the σ-calculus itself terminates. On the other hand, could the non-preservation of termination in the λs_e-calculus imply the non-termination of the s_e-calculus?

Selective colorimetric sensing for F by a cleft-shaped anion receptor containing amide and hydroxyl as recognition units

A simple cleft-shaped anion receptor 1 containing amide and hydroxyl as recognition units was synthesized and its anion recognition properties were investigated by naked-eye observation, UV–vis, fluorescence and ¹H NMR spectra. Receptor 1 could effectively recognize F⁻ via multiple H-bonding interactions, along with visible color change and remarkable fluorescence enhancement. Interestingly, reference compound 2 only containing amide groups did not display any interaction for all of the examined anions, including F⁻.     

Azo dyes featuring a pyrene unit: New selective chromogenic and fluorogenic chemodosimeters for Hg(II)

Three new chemodosimeters 1–3 were prepared, and their chromogenic and fluorogenic behaviors toward various metal cations were investigated. Receptors 1–3 show exclusive response toward Hg²⁺ ion and also distinguish Hg²⁺from other metal cations by different color changes in DMSO aqueous solution (DMSO/H₂O = 9/1). Among them, receptor 1 also exhibits a pronounced Hg²⁺-induced fluorescence enhancement. Thus, the receptor 1 can be used as a colorimetric and fluorescent chemodosimeter for the determination of Hg²⁺ ion. The use of the test strip of the receptor 1 to detect Hg²⁺ was also reported.     

Development of quality bounds for time and frequency domain models: application to the Shell distillation column

Statistical confidence bounds are developed for frequency response and step response models estimated from process input-output data using the frequency sampling filter model structure. The frequency domain bound is an extension of earlier work by the authors (Arifin et al., Journal of Process Control, 1995, 5, 71–76) and the time domain bound is a new result. These bounds provide the engineer with a measure of the quality of the estimated model, and therefore an indication of which aspects of the model are reliable and which aspects require further improvement. The Shell distillation column benchmark problem introduced by Cott (Journal of Process Control, 1995, 5, 60–70) is used for illustrative purposes.     

XRT– Exploring Runtime for .NET Architecture and Applications

XRT– Exploring Runtime – is an exploration framework for programs represented in Microsoft's common intermediate language (CIL). Processing .NET managed assemblies, it provides means for analyzing, rewriting, and executing the rewritten program. Whereas XRT's representation of state allows for arbitrary exploration strategies, it is particularly optimized for transactional exploration, where a transaction may consist of many instruction steps. XRT supports extensions, and one such extension is a module for symbolic exploration which captures the complete domain of safe CIL. Current applications of XRT are in the area of testing, namely parameterized unit testing and state-space exploration for model-based testing. This paper gives an overview of the architecture of XRT and outlines the applications.     

Restrictions of Minimum Spanner Problems

At-spanner of a graphGis a spanning subgraphHsuch that the distance between any two vertices inHis at mostttimes their distance inG. Spanners arise in the context of approximating the original graph with a sparse subgraph (Peleg, D., and Schäffer, A. A. (1989),J. Graph. Theory13(1), 99–116). The MINIMUMt-SPANNER problem seeks to find at-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values oft, on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994,Discrete Appl. Math.48, 187–194) and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994,Networks24, 233–249). We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners.     

The mean-shift outlier model in general weighted regression and its applications

Consider the general weighted linear regression model y=Xβ+, where E()=0, Cov()=Vσ², σ² is an unknown positive scalar, and V is a symmetric positive-definite matrix not necessary diagonal. Two models, the mean-shift outlier model and the case-deletion model, can be employed to develop multiple case-deletion diagnostics for the linear model. The multiple case-deletion diagnostics are obtained via the mean-shift outlier model in this article and are shown to be equivalent to the deletion diagnostics via the case deletion model obtained by Preisser and Qaqish (1996, Biometrika, 83, 551–562). In addition, computing the multiple case-deletion diagnostics obtained via the mean-shift outlier model is faster than computing the one based on the more commonly used case-deletion model in some situations. Applications of the multiple deletion diagnostics developed from the mean-shift outlier model are also given for regression analysis with the likelihood function available and regression analysis based on generalized estimating equations. These applications include survival models and the generalized estimating equations of Liang and Zeger (1986, Biometrika, 73, 13–22). Several numerical experiments as well as a real example are given as illustrations.     

Space–Time Block Coding for Channels with Intersymbol Interference

Stoica, P., and Lindskog, E., Space–Time Block Coding for Channels with Intersymbol Interference, Digital Signal Processing12 (2002) 616–627The downlink of many wireless communication systems can be a MISO channel. An important problem for a MISO channel is how to code across space and time to obtain the same ML receiver as for the corresponding SIMO channel. For flat fading channels, space–time block coding (STBC) is a recent breakthrough solution to this problem. In Lindskog and Paulraj (in Proceedings of ICC'2000, NewOrleans, LA, June 18–22, 2000), STBC has been generalized to channels with intersymbol interference (ISI) for the case of two transmit antennas and one receive antenna. In this paper we first revisit the generalized STBC scheme of Lindskog and Paulraj and show that it has the same appealing properties as the standard STBC for flat fading channels. Then we go on to present an extension of this scheme to ISI channels with any number of transmit and receive antennas.     

Unfair Problems and Randomized Algorithms for Metrical Task Systems

Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992,J. Assoc. Comput. Mach.39(4), 745–763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science,” pp. 197–207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.     

Probabilistic Logic over Paths

We introduce a probabilistic modal logic PPL extending the work of [Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1,2):78–128, 1990; Ronald Fagin and Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the ACM, 41(2):340–367, 1994] by allowing arbitrary nesting of a path probabilistic operator and we prove its completeness. We prove that our logic is strictly more expressive than other logics such as the logics cited above. By considering a probabilistic extension of CTL we show that this additional expressive power is really needed in some applications.     

Rule-Based Programming with Diaplan

Diaplan is a language for programming with graphs and diagrams that is currently being designed and implemented by the authors. In this paper, a programming example, declaration grids, shall illustrate how Diaplan supports a functional and object-oriented style of programming. The example also indicates which features are needed beyond those discussed in previous work on the language [B. Hoffmann, Abstraction and control for shapely nested graph transformation, Fundamenta Informaticae 58 (2003) 39–56].     

Roughness optimization for biomimetic superhydrophobic surfaces

For non-wetting liquids the contact angle with a rough surface is greater than with a flat surface and may approach 180°, as reported for leaves of water-repellent plants, such as lotus. Roughness affects the contact angle due to the increased area of solid–liquid interface and due to the effect of sharp edges of rough surfaces. High roughness may lead to composite solid–liquid–air interface, which may be either stable or unstable. A comprehensive analytical model is proposed to provide a relationship between local roughness and contact angle, which is used to develop roughness distribution and to create biomimetic superhydrophobic surfaces. Various roughness distributions are considered, including periodic and surfaces with rectangular, hemispherically topped cylindrical, conical and pyramidal asperities and the random Gaussian height distribution. Verification of the model is conducted using experimental data for the contact angle of water droplet on a lotus leaf surface. For two solid bodies in contact, for wetting liquids, wetting leads to the meniscus force, which affects friction. Dependence of the meniscus force on roughness, previously ignored, is considered in the paper and it is found that with increasing roughness meniscus force can grow due to scale effect.

Performance of STAP Tests in Gaussian and Compound-Gaussian Clutter

Michels, James H., Himed, Braham, and Rangaswamy, Muralidhar, Performance of STAP Tests in Gaussian and Compound-Gaussian Clutter, Digital Signal Processing, 10 (2000), 309–324.The performance of a recently proposed model-based space–time adaptive processing detection method is considered here and compared with several candidate algorithms. Specifically, we consider signal detection in additive disturbance consisting of compound-Gaussian clutter plus Gaussian thermal white noise. Consideration is given to both detection and constant false alarm rate robustness with respect to clutter texture power variations. Finally, the performance of the new test is assessed using small training data support size.     

On the computation of the Ratliff–Rush closure

Let R be a Cohen–Macaulay local ring with maximal ideal m. In this paper we present a procedure for computing the Ratliff–Rush closure of an m-primary ideal IR.     

Comonoids in chu: a large cartesian closed sibling of topological spaces

Com_K may be defined as the (cartesian closed) category of comonoids in chu_K, or equivalently as dictionaries D for which any crossword over D has its main diagonal in D. Com₂ resembles Top, ordinary topological spaces. Common to both are the Alexandroff posets and the Scott DCPOs, while the topological space and the dual DCPO {−∞ < … < −2 < −1 < 0} jointly witness the incomparability of Com₂ and Top. Such comonoids support a notion of bitopology admitting limits simultaneously for convergence and divergence. We raise the questions of whether a comonoid in chu₂ can be fully specified in terms of its specialization order and omitted cuts, and which cuts are optional. These questions have been actively pursued for four weeks as of this writing on the theory-edge mailing list in response to Puzzle 1.5 starting with http://groups.yahoo.com/group/theory-edge/messages/6957.