title: Properties of codes in rank metric

abstract: We study properties of rank metric and codes in rank metric over finite fields. We show that in rank metric perfect codes do not exist. We derive an existence bound that is the equivalent of the Gilbert--Varshamov bound in Hamming metric. We study the asymptotic behavior of the minimum rank distance of codes satisfying GV. We derive the probability distribution of minimum rank distance for random and random $\F{q}$-linear codes. We give an asymptotic equivalent of their average minimum rank distance and show that random $\F{q}$-linear codes are on GV bound for rank metric. We show that the covering density of optimum codes whose codewords can be seen as square matrices is lower bounded by a function depending only on the error-correcting capability of the codes. We show that there are quasi-perfect codes in rank metric over fields of characteristic 2.


title: Context-sensitive access to e-document corpus

abstract: The methodology of context-sensitive access to e-documents considers context as a problem model based on the knowledge extracted from the application domain, and presented in the form of application ontology. Efficient access to an information in the text form is needed. Wiki resources as a modern text format provides huge number of text in a semi formalized structure. At the first stage of the methodology, documents are indexed against the ontology representing macro-situation. The indexing method uses a topic tree as a middle layer between documents and the application ontology. At the second stage documents relevant to the current situation (the abstract and operational contexts) are identified and sorted by degree of relevance. Abstract context is a problem-oriented ontology-based model. Operational context is an instantiation of the abstract context with data provided by the information sources. The following parts of the methodology are described: (i) metrics for measuring similarity of e-documents to ontology, (ii) a document index storing results of indexing of e-documents against the ontology; (iii) a method for identification of relevant e-documents based on semantic similarity measures. Wikipedia (wiki resource) is used as a corpus of e-documents for approach evaluation in a case study. Text categorization, the presence of metadata, and an existence of a lot of articles related to different topics characterize the corpus.


title: Camera motion estimation through planar deformation determination

abstract: In this paper, we propose a global method for estimating the motion of a camera which films a static scene. Our approach is direct, fast and robust, and deals with adjacent frames of a sequence. It is based on a quadratic approximation of the deformation between two images, in the case of a scene with constant depth in the camera coordinate system. This condition is very restrictive but we show that provided translation and depth inverse variations are small enough, the error on optical flow involved by the approximation of depths by a constant is small. In this context, we propose a new model of camera motion, that allows to separate the image deformation in a similarity and a ``purely'' projective application, due to change of optical axis direction. This model leads to a quadratic approximation of image deformation that we estimate with an M-estimator; we can immediatly deduce camera motion parameters.


title: Comparing Typical Opening Move Choices Made by Humans and Chess Engines

abstract: The opening book is an important component of a chess engine, and thus computer chess programmers have been developing automated methods to improve the quality of their books. For chess, which has a very rich opening theory, large databases of high-quality games can be used as the basis of an opening book, from which statistics relating to move choices from given positions can be collected. In order to find out whether the opening books used by modern chess engines in machine versus machine competitions are ``comparable'' to those used by chess players in human versus human competitions, we carried out analysis on 26 test positions using statistics from two opening books one compiled from humans' games and the other from machines' games. Our analysis using several nonparametric measures, shows that, overall, there is a strong association between humans' and machines' choices of opening moves when using a book to guide their choices.


title: The Delay-Limited Capacity Region of OFDM Broadcast Channels

abstract: In this work, the delay limited capacity (DLC) of orthogonal frequency division multiplexing (OFDM) systems is investigated. The analysis is organized into two parts. In the first part, the impact of system parameters on the OFDM DLC is analyzed in a general setting. The main results are that under weak assumptions the maximum achievable single user DLC is almost independent of the distribution of the path attenuations in the low signal-to-noise (SNR) region but depends strongly on the delay spread. In the high SNR region the roles are exchanged. Here, the impact of delay spread is negligible while the impact of the distribution becomes dominant. The relevant asymptotic quantities are derived without employing simplifying assumptions on the OFDM correlation structure. Moreover, for both cases it is shown that the DLC is maximized if the total channel energy is uniformly spread, i.e. the power delay profile is uniform. It is worth pointing out that since universal bounds are obtained the results can also be used for other classes of parallel channels with block fading characteristic. The second part extends the setting to the broadcast channel and studies the corresponding OFDM DLC BC region. An algorithm for computing the OFDM BC DLC region is presented. To derive simple but smart resource allocation strategies, the principle of rate water-filling employing order statistics is introduced. This yields analytical lower bounds on the OFDM DLC region based on orthogonal frequency division multiple access (OFDMA) and ordinal channel state information (CSI). Finally, the schemes are compared to an algorithm using full CSI.


title: A type-based termination criterion for dependently-typed higher-order rewrite systems

abstract: Several authors devised type-based termination criteria for ML-like languages allowing non-structural recursive calls. We extend these works to general rewriting and dependent types, hence providing a powerful termination criterion for the combination of rewriting and beta-reduction in the Calculus of Constructions.


title: The Calculus of Algebraic Constructions

abstract: This paper is concerned with the foundations of the Calculus of Algebraic Constructions (CAC), an extension of the Calculus of Constructions by inductive data types. CAC generalizes inductive types equipped with higher-order primitive recursion, by providing definitions of functions by pattern-matching which capture recursor definitions for arbitrary non-dependent and non-polymorphic inductive types satisfying a strictly positivity condition. CAC also generalizes the first-order framework of abstract data types by providing dependent types and higher-order rewrite rules.


title: Termination and Confluence of Higher-Order Rewrite Systems

abstract: In the last twenty years, several approaches to higher-order rewriting have been proposed, among which Klop's Combinatory Rewrite Systems (CRSs), Nipkow's Higher-order Rewrite Systems (HRSs) and Jouannaud and Okada's higher-order algebraic specification languages, of which only the last one considers typed terms. The later approach has been extended by Jouannaud, Okada and the present author into Inductive Data Type Systems (IDTSs). In this paper, we extend IDTSs with the CRS higher-order pattern-matching mechanism, resulting in simply-typed CRSs. Then, we show how the termination criterion developed for IDTSs with first-order pattern-matching, called the General Schema, can be extended so as to prove the strong normalization of IDTSs with higher-order pattern-matching. Next, we compare the unified approach with HRSs. We first prove that the extended General Schema can also be applied to HRSs. Second, we show how Nipkow's higher-order critical pair analysis technique for proving local confluence can be applied to IDTSs.


title: Definitions by Rewriting in the Calculus of Constructions

abstract: The main novelty of this paper is to consider an extension of the Calculus of Constructions where predicates can be defined with a general form of rewrite rules. We prove the strong normalization of the reduction relation generated by the beta-rule and the user-defined rules under some general syntactic conditions including confluence. As examples, we show that two important systems satisfy these conditions: a sub-system of the Calculus of Inductive Constructions which is the basis of the proof assistant Coq, and the Natural Deduction Modulo a large class of equational theories.


title: Inductive-data-type Systems

abstract: In a previous work ("Abstract Data Type Systems", TCS 173(2), 1997), the last two authors presented a combined language made of a (strongly normalizing) algebraic rewrite system and a typed lambda-calculus enriched by pattern-matching definitions following a certain format, called the "General Schema", which generalizes the usual recursor definitions for natural numbers and similar "basic inductive types". This combined language was shown to be strongly normalizing. The purpose of this paper is to reformulate and extend the General Schema in order to make it easily extensible, to capture a more general class of inductive types, called "strictly positive", and to ease the strong normalization proof of the resulting system. This result provides a computation model for the combination of an algebraic specification language based on abstract data types and of a strongly typed functional language with strictly positive inductive types.


title: Language, logic and ontology: uncovering the structure of commonsense knowledge

abstract: The purpose of this paper is twofold: (i) we argue that the structure of commonsense knowledge must be discovered, rather than invented; and (ii) we argue that natural language, which is the best known theory of our (shared) commonsense knowledge, should itself be used as a guide to discovering the structure of commonsense knowledge. In addition to suggesting a systematic method to the discovery of the structure of commonsense knowledge, the method we propose seems to also provide an explanation for a number of phenomena in natural language, such as metaphor, intensionality, and the semantics of nominal compounds. Admittedly, our ultimate goal is quite ambitious, and it is no less than the systematic 'discovery' of a well-typed ontology of commonsense knowledge, and the subsequent formulation of the long-awaited goal of a meaning algebra.


title: Type theory and rewriting

abstract: We study the properties, in particular termination, of dependent types systems for lambda calculus and rewriting.


title: An Isabelle formalization of protocol-independent secrecy with an application to e-commerce

abstract: A protocol-independent secrecy theorem is established and applied to several non-trivial protocols. In particular, it is applied to protocols proposed for protecting the computation results of free-roaming mobile agents doing comparison shopping. All the results presented here have been formally proved in Isabelle by building on Larry Paulson's inductive approach. This therefore provides a library of general theorems that can be applied to other protocols.


title: Inductive types in the Calculus of Algebraic Constructions

abstract: In a previous work, we proved that almost all of the Calculus of Inductive Constructions (CIC), which is the basis of the proof assistant Coq, can be seen as a Calculus of Algebraic Constructions (CAC), an extension of the Calculus of Constructions with functions and predicates defined by higher-order rewrite rules. In this paper, we not only prove that CIC as a whole can be seen as a CAC, but also that it can be extended with non-free constructors, pattern-matching on defined symbols, non-strictly positive types and inductive-recursive types.


title: Rewriting modulo in Deduction modulo

abstract: We study the termination of rewriting modulo a set of equations in the Calculus of Algebraic Constructions, an extension of the Calculus of Constructions with functions and predicates defined by higher-order rewrite rules. In a previous work, we defined general syntactic conditions based on the notion of computable closure for ensuring the termination of the combination of rewriting and beta-reduction. Here, we show that this result is preserved when considering rewriting modulo a set of equations if the equivalence classes generated by these equations are finite, the equations are linear and satisfy general syntactic conditions also based on the notion of computable closure. This includes equations like associativity and commutativity, and provides an original treatment of termination modulo equations.


title: Definitions by rewriting in the Calculus of Constructions

abstract: This paper presents general syntactic conditions ensuring the strong normalization and the logical consistency of the Calculus of Algebraic Constructions, an extension of the Calculus of Constructions with functions and predicates defined by higher-order rewrite rules. On the one hand, the Calculus of Constructions is a powerful type system in which one can formalize the propositions and natural deduction proofs of higher-order logic. On the other hand, rewriting is a simple and powerful computation paradigm. The combination of both allows, among other things, to develop formal proofs with a reduced size and more automation compared with more traditional proof assistants. The main novelty is to consider a general form of rewriting at the predicate-level which generalizes the strong elimination of the Calculus of Inductive Constructions.


abstract: In a previous work, we proved that an important part of the Calculus of Inductive Constructions (CIC), the basis of the Coq proof assistant, can be seen as a Calculus of Algebraic Constructions (CAC), an extension of the Calculus of Constructions with functions and predicates defined by higher-order rewrite rules. In this paper, we prove that almost all CIC can be seen as a CAC, and that it can be further extended with non-strictly positive types and inductive-recursive types together with non-free constructors and pattern-matching on defined symbols.


title: Collaborative Decoding of Interleaved Reed-Solomon Codes and Concatenated Code Designs

abstract: Interleaved Reed-Solomon codes are applied in numerous data processing, data transmission, and data storage systems. They are generated by interleaving several codewords of ordinary Reed-Solomon codes. Usually, these codewords are decoded independently by classical algebraic decoding methods. However, by collaborative algebraic decoding approaches, such interleaved schemes allow the correction of error patterns beyond half the minimum distance, provided that the errors in the received signal occur in bursts. In this work, collaborative decoding of interleaved Reed-Solomon codes by multi-sequence shift-register synthesis is considered and analyzed. Based on the framework of interleaved Reed-Solomon codes, concatenated code designs are investigated, which are obtained by interleaving several Reed-Solomon codes, and concatenating them with an inner block code.


title: On Geometric Algebra representation of Binary Spatter Codes

abstract: Kanerva's Binary Spatter Codes are reformulated in terms of geometric algebra. The key ingredient of the construction is the representation of XOR binding in terms of geometric product.


title: Peano Count Trees (P-Trees) and Rule Association Mining for Gene Expression Profiling of Microarray Data

abstract: The greatest challenge in maximizing the use of gene expression data is to develop new computational tools capable of interconnecting and interpreting the results from different organisms and experimental settings. We propose an integrative and comprehensive approach including a super-chip containing data from microarray experiments collected on different species subjected to hypoxic and anoxic stress. A data mining technology called Peano count tree (P-trees) is used to represent genomic data in multidimensions. Each microarray spot is presented as a pixel with its corresponding red/green intensity feature bands. Each bad is stored separately in a reorganized 8-separate (bSQ) file format. Each bSQ is converted to a quadrant base tree structure (P-tree) from which a superchip is represented as expression P-trees (EP-trees) and repression P-trees (RP-trees). The use of association rule mining is proposed to derived to meanigingfully organize signal transduction pathways taking in consideration evolutionary considerations. We argue that the genetic constitution of an organism (K) can be represented by the total number of genes belonging to two groups. The group X constitutes genes (X1,Xn) and they can be represented as 1 or 0 depending on whether the gene was expressed or not. The second group of Y genes (Y1,Yn) is expressed at different levels. These genes have a very high repression, high expression, very repressed or highly repressed. However, many genes of the group Y are specie specific and modulated by the products and combinations of genes of the group X. In this paper, we introduce the dSQ and P-tree technology; the biological implications of association rule mining using X and Y gene groups and some advances in the integration of this information using the BRAIN architecture.


title: MIMO Broadcast Channels with Block Diagonalization and Finite Rate Feedback

abstract: Block diagonalization is a linear precoding technique for the multiple antenna broadcast (downlink) channel that involves transmission of multiple data streams to each receiver such that no multi-user interference is experienced at any of the receivers. This low-complexity scheme operates only a few dB away from capacity but does require very accurate channel knowledge at the transmitter, which can be very difficult to obtain in fading scenarios. We consider a limited feedback system where each receiver knows its channel perfectly, but the transmitter is only provided with a finite number of channel feedback bits from each receiver. Using a random vector quantization argument, we quantify the throughput loss due to imperfect channel knowledge as a function of the feedback level. The quality of channel knowledge must improve proportional to the SNR in order to prevent interference-limitations, and we show that scaling the number of feedback bits linearly with the system SNR is sufficient to maintain a bounded rate loss. Finally, we investigate a simple scalar quantization scheme that is seen to achieve the same scaling behavior as vector quantization.


title: Rapid Prototyping over IEEE 802.11

abstract: This paper introduces Prawn, a tool for prototyping communication protocols over IEEE 802.11 networks. Prawn allows researchers to conduct both functional assessment and performance evaluation as an inherent part of the protocol design process. Since Prawn runs on real IEEE 802.11 nodes, prototypes can be evaluated and adjusted under realistic conditions. Once the prototype has been extensively tested and thoroughly validated, and its functional design tuned accordingly, it is then ready for implementation. Prawn facilitates prototype development by providing: (i) a set of building blocks that implement common functions needed by a wide range of wireless protocols (e.g., neighbor discovery, link quality assessment, message transmission and reception), and (ii) an API that allows protocol designers to access Prawn primitives. We show through a number of case studies how Prawn supports prototyping as part of protocol design and, as a result of enabling deployment and testing under real-world scenarios, how Prawn provides useful feedback on protocol operation and performance.


title: An Enhanced Covering Lemma for Multiterminal Source Coding

abstract: An enhanced covering lemma for a Markov chain is proved in this paper, and then the distributed source coding problem of correlated general sources with one average distortion criterion under fixed-length coding is investigated. Based on the enhanced lemma, a sufficient and necessary condition for determining the achievability of rate-distortion triples is given.


title: Computable Closed Euclidean Subsets with and without Computable Points

abstract: The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskii, Tseitin, Kreisel, and Lacombe assert the existence of NON-empty co-r.e. closed sets devoid of computable points: sets which are `large' in the sense of positive Lebesgue measure. We observe that a certain size is in fact necessary: every non-empty co-r.e. closed real set without computable points has continuum cardinality. This leads us to investigate for various classes of computable real subsets whether they necessarily contain a (not necessarily effectively findable) computable point.


title: Semantics of Separation-Logic Typing and Higher-order Frame Rules for<br> Algol-like Languages

abstract: We show how to give a coherent semantics to programs that are well-specified in a version of separation logic for a language with higher types: idealized algol extended with heaps (but with immutable stack variables). In particular, we provide simple sound rules for deriving higher-order frame rules, allowing for local reasoning.


title: Theoretical analysis of network cranback protocols performance

abstract: Suggested the decision of the network cranback protocols performance analyzing problem from Eyal Felstine, Reuven Cohen and Ofer Hadar, " Crankback Prediction in Hierarchical ATM networks", Journal of Network and Systems Management, Vol. 10, No. 3, September 2002. It show that the false alarm probability and probability of successful way crossing can be calculated. The main optimization equations are developed for cranback protocol parameters by using analytical expressions for statistical protocol characteristics.


title: Estimation of the traffic in the binary channel for data networks

abstract: It is impossible to provide an effective utilization of communication networks without the analysis of the quantitative characteristics of the traffic in real time. The constant supervision of all channels of the data practically is impracticable because requires transfer of the significant additional information on a network and large resources expenses for devices of the control. Thus, the task on traffic estimation with small expenses in real time is the urgent.


title: Share and Disperse: How to Resist Against Aggregator Compromises in Sensor Networks

abstract: A common approach to overcome the limited nature of sensor networks is to aggregate data at intermediate nodes. A challenging issue in this context is to guarantee end-to-end security mainly because sensor networks are extremely vulnerable to node compromises. In order to secure data aggregation, in this paper we propose three schemes that rely on multipath routing. The first one guarantees data confidentiality through secret sharing, while the second and third ones provide data availability through information dispersal. Based on qualitative analysis and implementation, we show that, by applying these schemes, a sensor network can achieve data confidentiality, authenticity, and protection against denial of service attacks even in the presence of multiple compromised nodes.


title: Symbolic Simulation-Checking of Dense-Time Systems

abstract: Intuitively, an (implementation) automata is simulated by a (specification) automata if every externally observable transition by the implementation automata can also be made by the specification automata. In this work, we present a symbolic algorithm for the simulation-checking of timed automatas. We first present a simulation-checking procedure that operates on state spaces, representable with convex polyhedra, of timed automatas. We then present techniques to represent those intermediate result convex polyhedra with zones and make the procedure an algorithm. We then discuss how to handle Zeno states in the implementation automata. Finally, we have endeavored to realize the algorithm and report the performance of our algorithm in the experiment.


title: The central nature of the Hidden Subgroup problem

abstract: We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup for a large variety of groups. We also show that, over permutation groups, the decision version and search version of Hidden Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and its decision version.


title: An Application of the Mobile Transient Internet Architecture to IP Mobility and Inter-Operability

abstract: We introduce an application of a mobile transient network architecture on top of the current Internet. This paper is an application extension to a conceptual mobile network architecture. It attempts to specifically reinforce some of the powerful notions exposed by the architecture from an application perspective. Of these notions, we explore the network expansion layer, an overlay of components and services, that enables a persistent identification network and other required services. The overlay abstraction introduces several benefits of which mobility and communication across heterogenous network structures are of interest to this paper. We present implementations of several components and protocols including gateways, Agents and the Open Device Access Protocol. Our present identification network implementation exploits the current implementation of the Handle System through the use of distributed, global and persistent identifiers called handles. Handles are used to identify and locate devices and services abstracting any physical location or network association from the communicating ends. A communication framework is finally demonstrated that would allow for mobile devices on the public Internet to have persistent identifiers and thus be persistently accessible either directly or indirectly. This application expands IP inter-operability beyond its current boundaries.


title: Vector field visualization with streamlines

abstract: We have recently developed an algorithm for vector field visualization with oriented streamlines, able to depict the flow directions everywhere in a dense vector field and the sense of the local orientations. The algorithm has useful applications in the visualization of the director field in nematic liquid crystals. Here we propose an improvement of the algorithm able to enhance the visualization of the local magnitude of the field. This new approach of the algorithm is compared with the same procedure applied to the Line Integral Convolution (LIC) visualization.


title: Reversible Logic to Cryptographic Hardware: A New Paradigm

abstract: Differential Power Analysis (DPA) presents a major challenge to mathematically-secure cryptographic protocols. Attackers can break the encryption by measuring the energy consumed in the working digital circuit. To prevent this type of attack, this paper proposes the use of reversible logic for designing the ALU of a cryptosystem. Ideally, reversible circuits dissipate zero energy. Thus, it would be of great significance to apply reversible logic to designing secure cryptosystems. As far as is known, this is the first attempt to apply reversible logic to developing secure cryptosystems. In a prototype of a reversible ALU for a crypto-processor, reversible designs of adders and Montgomery multipliers are presented. The reversible designs of a carry propagate adder, four-to-two and five-to-two carry save adders are presented using a reversible TSG gate. One of the important properties of the TSG gate is that it can work singly as a reversible full adder. In order to design the reversible Montgomery multiplier, novel reversible sequential circuits are also proposed which are integrated with the proposed adders to design a reversible modulo multiplier. It is intended that this paper will provide a starting point for developing cryptosystems secure against DPA attacks.


title: Combined Integer and Floating Point Multiplication Architecture(CIFM) for FPGAs and Its Reversible Logic Implementation

abstract: In this paper, the authors propose the idea of a combined integer and floating point multiplier(CIFM) for FPGAs. The authors propose the replacement of existing 18x18 dedicated multipliers in FPGAs with dedicated 24x24 multipliers designed with small 4x4 bit multipliers. It is also proposed that for every dedicated 24x24 bit multiplier block designed with 4x4 bit multipliers, four redundant 4x4 multiplier should be provided to enforce the feature of self repairability (to recover from the faults). In the proposed CIFM reconfigurability at run time is also provided resulting in low power. The major source of motivation for providing the dedicated 24x24 bit multiplier stems from the fact that single precision floating point multiplier requires 24x24 bit integer multiplier for mantissa multiplication. A reconfigurable, self-repairable 24x24 bit multiplier (implemented with 4x4 bit multiply modules) will ideally suit this purpose, making FPGAs more suitable for integer as well floating point operations. A dedicated 4x4 bit multiplier is also proposed in this paper. Moreover, in the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. It is not possible to realize quantum computing without reversible logic. Thus, this paper also paper provides the reversible logic implementation of the proposed CIFM. The reversible CIFM designed and proposed here will form the basis of the completely reversible FPGAs.


title: On the Behavior of Journal Impact Factor Rank-Order Distribution

abstract: An empirical law for the rank-order behavior of journal impact factors is found. Using an extensive data base on impact factors including journals on Education, Agrosciences, Geosciences, Biosciences and Environ- mental, Chemical, Computer, Engineering, Material, Mathematical, Medical and Physical Sciences we have found extremely good fits out- performing other rank-order models. Some extensions to other areas of knowledge are discussed.


title: Happy endings for flip graphs

abstract: We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.


title: Semantic results for ontic and epistemic change

abstract: We give some semantic results for an epistemic logic incorporating dynamic operators to describe information changing events. Such events include epistemic changes, where agents become more informed about the non-changing state of the world, and ontic changes, wherein the world changes. The events are executed in information states that are modeled as pointed Kripke models. Our contribution consists of three semantic results. (i) Given two information states, there is an event transforming one into the other. The linguistic correspondent to this is that every consistent formula can be made true in every information state by the execution of an event. (ii) A more technical result is that: every event corresponds to an event in which the postconditions formalizing ontic change are assignments to `true' and `false' only (instead of assignments to arbitrary formulas in the logical language). `Corresponds' means that execution of either event in a given information state results in bisimilar information states. (iii) The third, also technical, result is that every event corresponds to a sequence of events wherein all postconditions are assignments of a single atom only (instead of simultaneous assignments of more than one atom).


title: Migrating Multi-page Web Applications to Single-page AJAX Interfaces

abstract: Recently, a new web development technique for creating interactive web applications, dubbed AJAX, has emerged. In this new model, the single-page web interface is composed of individual components which can be updated/replaced independently. With the rise of AJAX web applications classical multi-page web applications are becoming legacy systems. If until a year ago, the concern revolved around migrating legacy systems to web-based settings, today we have a new challenge of migrating web applications to single-page AJAX applications. Gaining an understanding of the navigational model and user interface structure of the source application is the first step in the migration process. In this paper, we explore how reverse engineering techniques can help analyze classic web applications for this purpose. Our approach, using a schema-based clustering technique, extracts a navigational model of web applications, and identifies candidate user interface components to be migrated to a single-page AJAX interface. Additionally, results of a case study, conducted to evaluate our tool, are presented.


title: Solving planning domains with polytree causal graphs is NP-complete

abstract: We show that solving planning domains on binary variables with polytree causal graph is \NP-complete. This is in contrast to a polynomial-time algorithm of Domshlak and Brafman that solves these planning domains for polytree causal graphs of bounded indegree.


title: Partial Evaluation for Program Comprehension

abstract: Program comprehension is the most tedious and time consuming task of software maintenance, an important phase of the software life cycle. This is particularly true while maintaining scientific application programs that have been written in Fortran for decades and that are still vital in various domains even though more modern languages are used to implement their user interfaces. Very often, programs have evolved as their application domains increase continually and have become very complex due to extensive modifications. This generality in programs is implemented by input variables whose value does not vary in the context of a given application. Thus, it is very interesting for the maintainer to propagate such information, that is to obtain a simplified program, which behaves like the initial one when used according to the restriction. We have adapted partial evaluation for program comprehension. Our partial evaluator performs mainly two tasks: constant propagation and statements simplification. It includes an interprocedural alias analysis. As our aim is program comprehension rather than optimization, there are two main differences with classical partial evaluation. We do not change the original


title: Reuse of Specification Patterns with the B Method

abstract: This paper describes an approach for reusing specification patterns. Specification patterns are design patterns that are expressed in a formal specification language. Reusing a specification pattern means instantiating it or composing it with other specification patterns. Three levels of composition are defined: juxtaposition, composition with inter-patterns links and unification. This paper shows through examples how to define specification patterns in B, how to reuse them directly in B, and also how to reuse the proofs associated with specification patterns.


title: Characterizing Solution Concepts in Games Using Knowledge-Based Programs

abstract: We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of \emph{knowledge-based programs}. Intuitively, all solution concepts are implementations of two knowledge-based programs, one appropriate for games represented in normal form, the other for games represented in extensive form. These knowledge-based programs can be viewed as embodying rationality. The representation works even if (a) information sets do not capture an agent's knowledge, (b) uncertainty is not represented by probability, or (c) the underlying game is not common knowledge.


title: Properties of Codes with the Rank Metric

abstract: In this paper, we study properties of rank metric codes in general and maximum rank distance (MRD) codes in particular. For codes with the rank metric, we first establish Gilbert and sphere-packing bounds, and then obtain the asymptotic forms of these two bounds and the Singleton bound. Based on the asymptotic bounds, we observe that asymptotically Gilbert-Varsharmov bound is exceeded by MRD codes and sphere-packing bound cannot be attained. We also establish bounds on the rank covering radius of maximal codes, and show that all MRD codes are maximal codes and all the MRD codes known so far achieve the maximum rank covering radius.


title: A Mobile Transient Internet Architecture

abstract: This paper describes a new architecture for transient mobile networks destined to merge existing and future network architectures, communication implementations and protocol operations by introducing a new paradigm to data delivery and identification. The main goal of our research is to enable seamless end-to-end communication between mobile and stationary devices across multiple networks and through multiple communication environments. The architecture establishes a set of infrastructure components and protocols that set the ground for a Persistent Identification Network (PIN). The basis for the operation of PIN is an identification space consisting of unique location independent identifiers similar to the ones implemented in the Handle system. Persistent Identifiers are used to identify and locate Digital Entities which can include devices, services, users and even traffic. The architecture establishes a primary connection independent logical structure that can operate over conventional networks or more advanced peer-to-peer aggregation networks. Communication is based on routing pools and novel protocols for routing data across several abstraction levels of the network, regardless of the end-points' current association and state...


title: Entropy generation in a model of reversible computation

abstract: We present a model in which, due to the quantum nature of the signals controlling the implementation time of successive unitary computational steps, \emph{physical} irreversibility appears in the execution of a \emph{logically} reversible computation.


title: Quantum communication is possible with pure state

abstract: It is believed that quantum communication is not possible with a pure ensemble of states because quantum entropy of pure state is zero. This is indeed possible due to geometric consequence of entanglement.


title: On the Secrecy Capacity of Fading Channels

abstract: We consider the secure transmission of information over an ergodic fading channel in the presence of an eavesdropper. Our eavesdropper can be viewed as the wireless counterpart of Wyner's wiretapper. The secrecy capacity of such a system is characterized under the assumption of asymptotically long coherence intervals. We first consider the full Channel State Information (CSI) case, where the transmitter has access to the channel gains of the legitimate receiver and the eavesdropper. The secrecy capacity under this full CSI assumption serves as an upper bound for the secrecy capacity when only the CSI of the legitimate receiver is known at the transmitter, which is characterized next. In each scenario, the perfect secrecy capacity is obtained along with the optimal power and rate allocation strategies. We then propose a low-complexity on/off power allocation strategy that achieves near-optimal performance with only the main channel CSI. More specifically, this scheme is shown to be asymptotically optimal as the average SNR goes to infinity, and interestingly, is shown to attain the secrecy capacity under the full CSI assumption. Remarkably, our results reveal the positive impact of fading on the secrecy capacity and establish the critical role of rate adaptation, based on the main channel CSI, in facilitating secure communications over slow fading channels.


title: ARQ Diversity in Fading Random Access Channels

abstract: A cross-layer optimization approach is adopted for the design of symmetric random access wireless systems. Instead of the traditional collision model, a more realistic physical layer model is considered. Based on this model, an Incremental Redundancy Automatic Repeat reQuest (IR-ARQ) scheme, tailored to jointly combat the effects of collisions, multi-path fading, and additive noise, is developed. The Diversity-Multiplexing-Delay tradeoff (DMDT) of the proposed scheme is analyzed for fully-loaded queues, and compared with that of Gallager tree algorithm for collision resolution and the network-assisted diversity multiple access (NDMA) protocol of Tsatsanis et al.. The fully-loaded queue model is then replaced by one with random arrivals, under which these protocols are compared in terms of the stability region, average delay and diversity gain. Overall, our analytical and numerical results establish the superiority of the proposed IR-ARQ scheme and reveal some important insights. For example, it turns out that the performance is optimized, for a given total throughput, by maximizing the probability that a certain user sends a new packet and minimizing the transmission rate employed by each user.


title: How To Break Anonymity of the Netflix Prize Dataset

abstract: We present a new class of statistical de-anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on. Our techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge. We apply our de-anonymization methodology to the Netflix Prize dataset, which contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's largest online movie rental service. We demonstrate that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset. Using the Internet Movie Database as the source of background knowledge, we successfully identified the Netflix records of known users, uncovering their apparent political preferences and other potentially sensitive information.


title: On the Error Exponents of ARQ Channels with Deadlines

abstract: We consider communication over Automatic Repeat reQuest (ARQ) memoryless channels with deadlines. In particular, an upper bound L is imposed on the maximum number of ARQ transmission rounds. In this setup, it is shown that incremental redundancy ARQ outperforms Forney's memoryless decoding in terms of the achievable error exponents.


title: Interference Channels with Common Information

abstract: In this paper, we consider the discrete memoryless interference channel with common information, in which two senders need deliver not only private messages but also certain common messages to their corresponding receivers. We derive an achievable rate region for such a channel by exploiting a random coding strategy, namely cascaded superposition coding. We reveal that the derived achievable rate region generalizes some important existing results for the interference channels with or without common information. Furthermore, we specialize to a class of deterministic interference channels with common information, and show that the derived achievable rate region is indeed the capacity region for this class of channels.


title: Doppler Spectrum Estimation by Ramanujan Fourier Transforms

abstract: The Doppler spectrum estimation of a weather radar signal in a classic way can be made by two methods, temporal one based in the autocorrelation of the successful signals, whereas the other one uses the estimation of the power spectral density PSD by using Fourier transforms. We introduces a new tool of signal processing based on Ramanujan sums cq(n), adapted to the analysis of arithmetical sequences with several resonances p/q. These sums are almost periodic according to time n of resonances and aperiodic according to the order q of resonances. New results will be supplied by the use of Ramanujan Fourier Transform (RFT) for the estimation of the Doppler spectrum for the weather radar signal.


title: Intrusion detection mechanisms for VoIP applications

abstract: VoIP applications are emerging today as an important component in business and communication industry. In this paper, we address the intrusion detection and prevention in VoIP networks and describe how a conceptual solution based on the Bayes inference approach can be used to reinforce the existent security mechanisms. Our approach is based on network monitoring and analyzing of the VoIP-specific traffic. We give a detailed example on attack detection using the SIP signaling protocol.


title: Stochastic Formal Methods for Hybrid Systems

abstract: We provide a framework to bound the probability that accumulated errors were never above a given threshold on hybrid systems. Such systems are used for example to model an aircraft or a nuclear power plant on one side and its software on the other side. This report contains simple formulas based on L\'evy's and Markov's inequalities and it presents a formal theory of random variables with a special focus on producing concrete results. We selected four very common applications that fit in our framework and cover the common practices of hybrid systems that evolve for a long time. We compute the number of bits that remain continuously significant in the first two applications with a probability of failure around one against a billion, where worst case analysis considers that no significant bit remains. We are using PVS as such formal tools force explicit statement of all hypotheses and prevent incorrect uses of theorems.


title: Local approximate inference algorithms

abstract: We present a new local approximation algorithm for computing Maximum a Posteriori (MAP) and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\em appropriately} chosen small components; then computing estimates locally in each of these components and then producing a {\em good} global solution. We show that if the underlying graph $G$ either excludes some finite-sized graph as its minor (e.g. Planar graph) or has low doubling dimension (e.g. any graph with {\em geometry}), then our algorithm will produce solution for both questions within {\em arbitrary accuracy}. We present a message-passing implementation of our algorithm for MAP computation using self-avoiding walk of graph. In order to evaluate the computational cost of this implementation, we derive novel tight bounds on the size of self-avoiding walk tree for arbitrary graph. As a consequence of our algorithmic result, we show that the normalized log-partition function (also known as free-energy) for a class of {\em regular} MRFs will converge to a limit, that is computable to an arbitrary accuracy.


title: On the Performance of Lossless Joint Source-Channel Coding Based on Linear Codes

abstract: A general lossless joint source-channel coding scheme based on linear codes is proposed and then analyzed in this paper. It is shown that a linear code with good joint spectrum can be used to establish limit-approaching joint source-channel coding schemes for arbitrary sources and channels, where the joint spectrum of the code is a generalization of the input-output weight distribution.


title: CHAC. A MOACO Algorithm for Computation of Bi-Criteria Military Unit Path in the Battlefield

abstract: In this paper we propose a Multi-Objective Ant Colony Optimization (MOACO) algorithm called CHAC, which has been designed to solve the problem of finding the path on a map (corresponding to a simulated battlefield) that minimizes resources while maximizing safety. CHAC has been tested with two different state transition rules: an aggregative function that combines the heuristic and pheromone information of both objectives and a second one that is based on the dominance concept of multiobjective optimization problems. These rules have been evaluated in several different situations (maps with different degree of difficulty), and we have found that they yield better results than a greedy algorithm (taken as baseline) in addition to a military behaviour that is also better in the tactical sense. The aggregative function, in general, yields better results than the one based on dominance.


title: Instant Computing - A New Computation Paradigm

abstract: Voltage peaks on a conventional computer's power lines allow for the well-known dangerous DPA attacks. We show that measurement of a quantum computer's transient state during a computational step reveals information about a complete computation of arbitrary length, which can be extracted by repeated probing, if the computer is suitably programmed. Instant computing, as we name this mode of operation, recognizes for any total or partial recursive function arguments lying in the domain of definition and yields their function value with arbitrary small error probability in probabilistic linear time. This implies recognition of (not necessarily recursively enumerable) complements of recursively enumerable sets and the solution of the halting problem. Future quantum computers are shown to be likely to allow for instant computing, and some consequences are pointed out.


title: An Achievable Rate Region for the Gaussian Interference Channel

abstract: An achievable rate region for the Gaussian interference channel is derived using Sato's modified frequency division multiplexing idea and a special case of Han and Kobayashi's rate region (denoted by $\Gmat^\prime$). We show that the new inner bound includes $\Gmat^\prime$, Sason's rate region $\Dmat$, as well as the achievable region via TDM/FDM, as its subsets. The advantage of this improved inner bound over $\Gmat^\prime$ arises due to its inherent ability to utilize the whole transmit power range on the real line without violating the power constraint. We also provide analysis to examine the conditions for the new achievable region to strictly extend $\Gmat^\prime$.


title: DepAnn - An Annotation Tool for Dependency Treebanks

abstract: DepAnn is an interactive annotation tool for dependency treebanks, providing both graphical and text-based annotation interfaces. The tool is aimed for semi-automatic creation of treebanks. It aids the manual inspection and correction of automatically created parses, making the annotation process faster and less error-prone. A novel feature of the tool is that it enables the user to view outputs from several parsers as the basis for creating the final tree to be saved to the treebank. DepAnn uses TIGER-XML, an XML-based general encoding format for both, representing the parser outputs and saving the annotated treebank. The tool includes an automatic consistency checker for sentence structures. In addition, the tool enables users to build structures manually, add comments on the annotations, modify the tagsets, and mark sentences for further revision.


title: Quantifier elimination for the reals with a predicate for the powers of two

abstract: In 1985, van den Dries showed that the theory of the reals with a predicate for the integer powers of two admits quantifier elimination in an expanded language, and is hence decidable. He gave a model-theoretic argument, which provides no apparent bounds on the complexity of a decision procedure. We provide a syntactic argument that yields a procedure that is primitive recursive, although not elementary. In particular, we show that it is possible to eliminate a single block of existential quantifiers in time $2^0_{O(n)}$, where $n$ is the length of the input formula and $2_k^x$ denotes $k$-fold iterated exponentiation.


title: Applying Part-of-Seech Enhanced LSA to Automatic Essay Grading

abstract: Latent Semantic Analysis (LSA) is a widely used Information Retrieval method based on "bag-of-words" assumption. However, according to general conception, syntax plays a role in representing meaning of sentences. Thus, enhancing LSA with part-of-speech (POS) information to capture the context of word occurrences appears to be theoretically feasible extension. The approach is tested empirically on a automatic essay grading system using LSA for document similarity comparisons. A comparison on several POS-enhanced LSA models is reported. Our findings show that the addition of contextual information in the form of POS tags can raise the accuracy of the LSA-based scoring models up to 10.77 per cent.


title: Approximate Convex Optimization by Online Game Playing

abstract: Lagrangian relaxation and approximate optimization algorithms have received much attention in the last two decades. Typically, the running time of these methods to obtain a $\epsilon$ approximate solution is proportional to $\frac{1}{\epsilon^2}$. Recently, Bienstock and Iyengar, following Nesterov, gave an algorithm for fractional packing linear programs which runs in $\frac{1}{\epsilon}$ iterations. The latter algorithm requires to solve a convex quadratic program every iteration - an optimization subroutine which dominates the theoretical running time. We give an algorithm for convex programs with strictly convex constraints which runs in time proportional to $\frac{1}{\epsilon}$. The algorithm does NOT require to solve any quadratic program, but uses gradient steps and elementary operations only. Problems which have strictly convex constraints include maximum entropy frequency estimation, portfolio optimization with loss risk constraints, and various computational problems in signal processing. As a side product, we also obtain a simpler version of Bienstock and Iyengar's result for general linear programming, with similar running time. We derive these algorithms using a new framework for deriving convex optimization algorithms from online game playing algorithms, which may be of independent interest.


title: Classdesc and Graphcode: support for scientific programming in C++

abstract: Object-oriented programming languages such as Java and Objective C have become popular for implementing agent-based and other object-based simulations since objects in those languages can {\em reflect} (i.e. make runtime queries of an object's structure). This allows, for example, a fairly trivial {\em serialisation} routine (conversion of an object into a binary representation that can be stored or passed over a network) to be written. However C++ does not offer this ability, as type information is thrown away at compile time. Yet C++ is often a preferred development environment, whether for performance reasons or for its expressive features such as operator overloading. In scientific coding, changes to a model's codes takes place constantly, as the model is refined, and different phenomena are studied. Yet traditionally, facilities such as checkpointing, routines for initialising model parameters and analysis of model output depend on the underlying model remaining static, otherwise each time a model is modified, a whole slew of supporting routines needs to be changed to reflect the new data structures. Reflection offers the advantage of the simulation framework adapting to the underlying model without programmer intervention, reducing the effort of modifying the model. In this paper, we present the {\em Classdesc} system which brings many of the benefits of object reflection to C++, {\em ClassdescMP} which dramatically simplifies coding of MPI based parallel programs and {\em Graphcode} a general purpose data parallel programming environment.


title: Construction algorithm for network error-correcting codes attaining the Singleton bound

abstract: We give a centralized deterministic algorithm for constructing linear network error-correcting codes that attain the Singleton bound of network error-correcting codes. The proposed algorithm is based on the algorithm by Jaggi et al. We give estimates on the time complexity and the required symbol size of the proposed algorithm. We also estimate the probability of a random choice of local encoding vectors by all intermediate nodes giving a network error-correcting codes attaining the Singleton bound. We also clarify the relationship between the robust network coding and the network error-correcting codes with known locations of errors.


title: Faithful Polynomial Evaluation with Compensated Horner Algorithm

abstract: This paper presents two sufficient conditions to ensure a faithful evaluation of polynomial in IEEE-754 floating point arithmetic. Faithfulness means that the computed value is one of the two floating point neighbours of the exact result; it can be satisfied using a more accurate algorithm than the classic Horner scheme. One condition here provided is an apriori bound of the polynomial condition number derived from the error analysis of the compensated Horner algorithm. The second condition is both dynamic and validated to check at the running time the faithfulness of a given evaluation. Numerical experiments illustrate the behavior of these two conditions and that associated running time over-cost is really interesting.


title: Proof Nets and the Identity of Proofs

abstract: These are the notes for a 5-lecture-course given at ESSLLI 2006 in Malaga, Spain. The URL of the school is http://esslli2006.lcc.uma.es/ . This version slightly differs from the one which has been distributed at the school because typos have been removed and comments and suggestions by students have been worked in. The course is intended to be introductory. That means no prior knowledge of proof nets is required. However, the student should be familiar with the basics of propositional logic, and should have seen formal proofs in some formal deductive system (e.g., sequent calculus, natural deduction, resolution, tableaux, calculus of structures, Frege-Hilbert-systems, ...). It is probably helpful if the student knows already what cut elimination is, but this is not strictly necessary. In these notes, I will introduce the concept of ``proof nets'' from the viewpoint of the problem of the identity of proofs. I will proceed in a rather informal way. The focus will be more on presenting ideas than on presenting technical details. The goal of the course is to give the student an overview of the theory of proof nets and make the vast amount of literature on the topic easier accessible to the beginner. For introducing the basic concepts of the theory, I will in the first part of the course stick to the unit-free multiplicative fragment of linear logic because of its rather simple notion of proof nets. In the second part of the course we will see proof nets for more sophisticated logics. This is a basic introduction into proof nets from the perspective of the identity of proofs. We discuss how deductive proofs can be translated into proof nets and what a correctness criterion is.


title: Dependency Treebanks: Methods, Annotation Schemes and Tools

abstract: In this paper, current dependencybased treebanks are introduced and analyzed. The methods used for building the resources, the annotation schemes applied, and the tools used (such as POS taggers, parsers and annotation software) are discussed.


title: Report on article: P=NP Linear programming formulation of the Traveling Salesman Problem

abstract: This article presents counter examples for three articles claiming that P=NP. Articles for which it applies are: Moustapha Diaby "P = NP: Linear programming formulation of the traveling salesman problem" and "Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem", and also Sergey Gubin "A Polynomial Time Algorithm for The Traveling Salesman Problem"


title: Fitness Uniform Optimization

abstract: In evolutionary algorithms, the fitness of a population increases with time by mutating and recombining individuals and by a biased selection of more fit individuals. The right selection pressure is critical in ensuring sufficient optimization progress on the one hand and in preserving genetic diversity to be able to escape from local optima on the other hand. Motivated by a universal similarity relation on the individuals, we propose a new selection scheme, which is uniform in the fitness values. It generates selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness, as is the case for all other selection schemes. We show analytically on a simple example that the new selection scheme can be much more effective than standard selection schemes. We also propose a new deletion scheme which achieves a similar result via deletion and show how such a scheme preserves genetic diversity more effectively than standard approaches. We compare the performance of the new schemes to tournament selection and random deletion on an artificial deceptive problem and a range of NP-hard problems: traveling salesman, set covering and satisfiability.


title: The intersection and the union of the asynchronous systems

abstract: The asynchronous systems $f$ are the models of the asynchronous circuits from digital electrical engineering. They are multi-valued functions that associate to each input $u:\mathbf{R}\to \{0,1\}^{m}$ a set of states $x\in f(u),$ where $x:\mathbf{R}\to \{0,1\}^{n}.$ The intersection of the systems allows adding supplementary conditions in modeling and the union of the systems allows considering the validity of one of two systems in modeling, for example when testing the asynchronous circuits and the circuit is supposed to be 'good' or 'bad'. The purpose of the paper is that of analyzing the intersection and the union against the initial/final states, initial/final time, initial/final state functions, subsystems, dual systems, inverse systems, Cartesian product of systems, parallel connection and serial connection of systems.


title: Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays

abstract: Local moments are used for local regression, to compute statistical measures such as sums, averages, and standard deviations, and to approximate probability distributions. We consider the case where the data source is a very large I/O array of size n and we want to compute the first N local moments, for some constant N. Without precomputation, this requires O(n) time. We develop a sequence of algorithms of increasing sophistication that use precomputation and additional buffer space to speed up queries. The simpler algorithms partition the I/O array into consecutive ranges called bins, and they are applicable not only to local-moment queries, but also to algebraic queries (MAX, AVERAGE, SUM, etc.). With N buffers of size sqrt{n}, time complexity drops to O(sqrt n). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity (O(b log_b n)), when using N hierarchical buffers of size n/b. Using Overlapped Bin Buffering, we show that only a single buffer is needed, as with wavelet-based algorithms, but using much less storage. Applications exist in multidimensional and statistical databases over massive data sets, interactive image processing, and visualization.


title: Community Detection in Complex Networks Using Agents

abstract: Community structure identification has been one of the most popular research areas in recent years due to its applicability to the wide scale of disciplines. To detect communities in varied topics, there have been many algorithms proposed so far. However, most of them still have some drawbacks to be addressed. In this paper, we present an agent-based based community detection algorithm. The algorithm that is a stochastic one makes use of agents by forcing them to perform biased moves in a smart way. Using the information collected by the traverses of these agents in the network, the network structure is revealed. Also, the network modularity is used for determining the number of communities. Our algorithm removes the need for prior knowledge about the network such as number of the communities or any threshold values. Furthermore, the definite community structure is provided as a result instead of giving some structures requiring further processes. Besides, the computational and time costs are optimized because of using thread like working agents. The algorithm is tested on three network data of different types and sizes named Zachary karate club, college football and political books. For all three networks, the real network structures are identified in almost every run.


title: On Bounds for $E$-capacity of DMC

abstract: Random coding, expurgated and sphere packing bounds are derived by method of types and method of graph decomposition for $E$-capacity of discrete memoryless channel (DMC). Three decoding rules are considered, the random coding bound is attainable by each of the three rules, but the expurgated bound is achievable only by maximum-likelihood decoding. Sphere packing bound is obtained by very simple combinatorial reasonings of the method of types. The paper joins and reviews the results of previous hard achievable publications.


title: Scheduling and data redistribution strategies on star platforms

abstract: In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.


title: List Decoding of Hermitian Codes using Groebner Bases

abstract: List decoding of Hermitian codes is reformulated to allow an efficient and simple algorithm for the interpolation step. The algorithm is developed using the theory of Groebner bases of modules. The computational complexity of the algorithm seems comparable to previously known algorithms achieving the same task, and the algorithm is better suited for hardware implementation.


title: P2P IPTV Measurement: A Comparison Study

abstract: With the success of P2P file sharing, new emerging P2P applications arise on the Internet for streaming content like voice (VoIP) or live video (IPTV). Nowadays, there are lots of works measuring P2P file sharing or P2P telephony systems, but there is still no comprehensive study about P2P IPTV, whereas it should be massively used in the future. During the last FIFA world cup, we measured network traffic generated by P2P IPTV applications like PPlive, PPstream, TVants and Sopcast. In this paper we analyze some of our results during the same games for the applications. We focus on traffic statistics and churn of peers within these P2P networks. Our objectives are threefold: we point out the traffic generated to understand the impact they will have on the network, we try to infer the mechanisms of such applications and highlight differences, and we give some insights about the users' behavior.


title: A Markov Chain based method for generating long-range dependence

abstract: This paper describes a model for generating time series which exhibit the statistical phenomenon known as long-range dependence (LRD). A Markov Modulated Process based upon an infinite Markov chain is described. The work described is motivated by applications in telecommunications where LRD is a known property of time-series measured on the internet. The process can generate a time series exhibiting LRD with known parameters and is particularly suitable for modelling internet traffic since the time series is in terms of ones and zeros which can be interpreted as data packets and inter-packet gaps. The method is extremely simple computationally and analytically and could prove more tractable than other methods described in the literature


title: Markov-modulated on/off processes for long-range dependent internet traffic

abstract: The aim of this paper is to use a very simple queuing model to compare a number of models from the literature which have been used to replicate the statistical nature of internet traffic and, in particular, the long-range dependence of this traffic. The four models all have the form of discrete time Markov-modulated processes (two other models are introduced for comparison purposes). While it is often stated that long-range dependence has a critical effect on queuing performance, it appears that the models used here do not well replicated the queuing performance of real internet traffic. In particular, they fail to replicate the mean queue length (and hence the mean delay) and the probability of the queue length exceeding a given level.


title: Bounds on the coefficients of the characteristic and minimal polynomials

abstract: This note presents absolute bounds on the size of the coefficients of the characteristic and minimal polynomials depending on the size of the coefficients of the associated matrix. Moreover, we present algorithms to compute more precise input-dependant bounds on these coefficients. Such bounds are e.g. useful to perform deterministic chinese remaindering of the characteristic or minimal polynomial of an integer matrix.


title: A Concurrent Calculus with Atomic Transactions

abstract: The Software Transactional Memory (STM) model is an original approach for controlling concurrent accesses to ressources without the need for explicit lock-based synchronization mechanisms. A key feature of STM is to provide a way to group sequences of read and write actions inside atomic blocks, similar to database transactions, whose whole effect should occur atomically. In this paper, we investigate STM from a process algebra perspective and define an extension of asynchronous CCS with atomic blocks of actions. Our goal is not only to set a formal ground for reasoning on STM implementations but also to understand how this model fits with other concurrency control mechanisms. We also view this calculus as a test bed for extending process calculi with atomic transactions. This is an interesting direction for investigation since, for the most part, actual works that mix transactions with process calculi consider compensating transactions, a model that lacks all the well-known ACID properties. We show that the addition of atomic transactions results in a very expressive calculus, enough to easily encode other concurrent primitives such as guarded choice and multiset-synchronization (\`{a} la join-calculus). The correctness of our encodings is proved using a suitable notion of bisimulation equivalence. The equivalence is then applied to prove interesting ``laws of transactions'' and to obtain a simple normal form for transactions.


title: Why block length and delay behave differently if feedback is present

abstract: For output-symmetric DMCs at even moderately high rates, fixed-block-length communication systems show no improvements in their error exponents with feedback. In this paper, we study systems with fixed end-to-end delay and show that feedback generally provides dramatic gains in the error exponents. A new upper bound (the uncertainty-focusing bound) is given on the probability of symbol error in a fixed-delay communication system with feedback. This bound turns out to have a similar form to Viterbi's bound used for the block error probability of convolutional codes as a function of the fixed constraint length. The uncertainty-focusing bound is shown to be asymptotically achievable with noiseless feedback for erasure channels as well as any output-symmetric DMC that has strictly positive zero-error capacity. Furthermore, it can be achieved in a delay-universal (anytime) fashion even if the feedback itself is delayed by a small amount. Finally, it is shown that for end-to-end delay, it is generally possible at high rates to beat the sphere-packing bound for general DMCs -- thereby providing a counterexample to a conjecture of Pinsker.


title: How to beat the sphere-packing bound with feedback

abstract: The sphere-packing bound $E_{sp}(R)$ bounds the reliability function for fixed-length block-codes. For symmetric channels, it remains a valid bound even when strictly causal noiseless feedback is allowed from the decoder to the encoder. To beat the bound, the problem must be changed. While it has long been known that variable-length block codes can do better when trading-off error probability with expected block-length, this correspondence shows that the {\em fixed-delay} setting also presents such an opportunity for generic channels. While $E_{sp}(R)$ continues to bound the tradeoff between bit error and fixed end-to-end latency for symmetric channels used {\em without} feedback, a new bound called the ``focusing bound'' gives the limits on what can be done with feedback. If low-rate reliable flow-control is free (ie. the noisy channel has strictly positive zero-error capacity), then the focusing bound can be asymptotically achieved. Even when the channel has no zero-error capacity, it is possible to substantially beat the sphere-packing bound by synthesizing an appropriately reliable channel to carry the flow-control information.


title: Constant for associative patterns ensemble

abstract: Creation procedure of associative patterns ensemble in terms of formal logic with using neural net-work (NN) model is formulated. It is shown that the associative patterns set is created by means of unique procedure of NN work which having individual parameters of entrance stimulus transformation. It is ascer-tained that the quantity of the selected associative patterns possesses is a constant.


title: Stabilization using both noisy and noiseless feedback

abstract: When designing a distributed control system, the system designer has a choice in how to connect the different units through communication channels. In practice, noiseless and noisy channels may coexist. Using the standard toy example of scalar stabilization, this paper shows how a small amount of noiseless feedback can perform a ``supervisory'' role and thereby boost the effectiveness of noisy feedback.


title: Coding into a source: a direct inverse Rate-Distortion theorem

abstract: Shannon proved that if we can transmit bits reliably at rates larger than the rate distortion function $R(D)$, then we can transmit this source to within a distortion $D$. We answer the converse question ``If we can transmit a source to within a distortion $D$, can we transmit bits reliably at rates less than the rate distortion function?'' in the affirmative. This can be viewed as a direct converse of the rate distortion theorem.


title: Source coding and channel requirements for unstable processes

abstract: Our understanding of information in systems has been based on the foundation of memoryless processes. Extensions to stable Markov and auto-regressive processes are classical. Berger proved a source coding theorem for the marginally unstable Wiener process, but the infinite-horizon exponentially unstable case has been open since Gray's 1970 paper. There were also no theorems showing what is needed to communicate such processes across noisy channels. In this work, we give a fixed-rate source-coding theorem for the infinite-horizon problem of coding an exponentially unstable Markov process. The encoding naturally results in two distinct bitstreams that have qualitatively different QoS requirements for communicating over a noisy medium. The first stream captures the information that is accumulating within the nonstationary process and requires sufficient anytime reliability from the channel used to communicate the process. The second stream captures the historical information that dissipates within the process and is essentially classical. This historical information can also be identified with a natural stable counterpart to the unstable process. A converse demonstrating the fundamentally layered nature of unstable sources is given by means of information-embedding ideas.


title: Lossless coding for distributed streaming sources

abstract: Distributed source coding is traditionally viewed in the block coding context -- all the source symbols are known in advance at the encoders. This paper instead considers a streaming setting in which iid source symbol pairs are revealed to the separate encoders in real time and need to be reconstructed at the decoder with some tolerable end-to-end delay using finite rate noiseless channels. A sequential random binning argument is used to derive a lower bound on the error exponent with delay and show that both ML decoding and universal decoding achieve the same positive error exponents inside the traditional Slepian-Wolf rate region. The error events are different from the block-coding error events and give rise to slightly different exponents. Because the sequential random binning scheme is also universal over delays, the resulting code eventually reconstructs every source symbol correctly with probability 1.


title: A Simple Converse of Burnashev's Reliability

abstract: In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.


title: The necessity and sufficiency of anytime capacity for stabilization of a linear system over a noisy communication link, Part II: vector systems

abstract: In part I, we reviewed how Shannon's classical notion of capacity is not sufficient to characterize a noisy communication channel if the channel is intended to be used as part of a feedback loop to stabilize an unstable scalar linear system. While classical capacity is not enough, a sense of capacity (parametrized by reliability) called "anytime capacity" is both necessary and sufficient for channel evaluation in this context. The rate required is the log of the open-loop system gain and the required reliability comes from the desired sense of stability. Sufficiency is maintained even in cases with noisy observations and without any explicit feedback between the observer and the controller. This established the asymptotic equivalence between scalar stabilization problems and delay-universal communication problems with feedback. Here in part II, the vector-state generalizations are established and it is the magnitudes of the unstable eigenvalues that play an essential role. To deal with such systems, the concept of the anytime rate-region is introduced. This is the region of rates that the channel can support while still meeting potentially different anytime reliability targets for parallel message streams. All the scalar results generalize on an eigenvalue by eigenvalue basis. When there is no explicit feedback of the noisy channel outputs, the intrinsic delay of the unstable system tells us what the feedback delay needs to be while evaluating the anytime-rate-region for the channel. An example involving a binary erasure channel is used to illustrate how differentiated service is required in any separation-based control architecture.


title: Grooming of Dynamic Traffic in WDM Star and Tree Networks Using Genetic Algorithm

abstract: The advances in WDM technology lead to the great interest in traffic grooming problems. As traffic often changes from time to time, the problem of grooming dynamic traffic is of great practical value. In this paper, we discuss dynamic grooming of traffic in star and tree networks. A genetic algorithm (GA) based approach is proposed to support arbitrary dynamic traffic patterns, which minimizes the number of ADM's and wavelengths. To evaluate the algorithm, tighter bounds are derived. Computer simulation results show that our algorithm is efficient in reducing both the numbers of ADM's and wavelengths in tree and star networks.


title: Decoder Error Probability of MRD Codes

abstract: In this paper, we first introduce the concept of elementary linear subspace, which has similar properties to those of a set of coordinates. Using this new concept, we derive properties of maximum rank distance (MRD) codes that parallel those of maximum distance separable (MDS) codes. Using these properties, we show that the decoder error probability of MRD codes with error correction capability t decreases exponentially with t^2 based on the assumption that all errors with the same rank are equally likely. We argue that the channel based on this assumption is an approximation of a channel corrupted by crisscross errors.


title: Canonical decomposition of catenation of factorial languages

abstract: According to a previous result by S. V. Avgustinovich and the author, each factorial language admits a unique canonical decomposition to a catenation of factorial languages. In this paper, we analyze the appearance of the canonical decomposition of a catenation of two factorial languages whose canonical decompositions are given.


title: On LAO Testing of Multiple Hypotheses for Many Independent Objects

abstract: The problem of many hypotheses logarithmically asymptotically optimal (LAO) testing for a model consisting of three or more independent objects is solved. It is supposed that $M$ probability distributions are known and each object independently of others follows to one of them. The matrix of asymptotic interdependencies (reliability--reliability functions) of all possible pairs of the error probability exponents (reliabilities) in optimal testing for this model is studied. This problem was introduced (and solved for the case of two objects and two given probability distributions) by Ahlswede and Haroutunian. The model with two independent objects with $M$ hypotheses was explored by Haroutunian and Hakobyan.


title: Anytime coding on the infinite bandwidth AWGN channel: A sequential semi-orthogonal optimal code

abstract: It is well known that orthogonal coding can be used to approach the Shannon capacity of the power-constrained AWGN channel without a bandwidth constraint. This correspondence describes a semi-orthogonal variation of pulse position modulation that is sequential in nature -- bits can be ``streamed across'' without having to buffer up blocks of bits at the transmitter. ML decoding results in an exponentially small probability of error as a function of tolerated receiver delay and thus eventually a zero probability of error on every transmitted bit. In the high-rate regime, a matching upper bound is given on the delay error exponent. We close with some comments on the case with feedback and the connections to the capacity per unit cost problem.


title: An unbreakable cryptosystem for common people

abstract: It has been found that an algorithm can generate true random numbers on classical computer. The algorithm can be used to generate unbreakable message PIN (personal identification number) and password.


title: Most Programs Stop Quickly or Never Halt

abstract: Since many real-world problems arising in the fields of compiler optimisation, automated software engineering, formal proof systems, and so forth are equivalent to the Halting Problem--the most notorious undecidable problem--there is a growing interest, not only academically, in understanding the problem better and in providing alternative solutions. Halting computations can be recognised by simply running them; the main difficulty is to detect non-halting programs. Our approach is to have the probability space extend over both space and time and to consider the probability that a random $N$-bit program has halted by a random time. We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k>0, we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than 2^{-k}. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that ``long'' runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time 2^{N+constant} has effectively zero density.


title: Usage Impact Factor: the effects of sample characteristics on usage-based impact metrics

abstract: There exist ample demonstrations that indicators of scholarly impact analogous to the citation-based ISI Impact Factor can be derived from usage data. However, contrary to the ISI IF which is based on citation data generated by the global community of scholarly authors, so far usage can only be practically recorded at a local level leading to community-specific assessments of scholarly impact that are difficult to generalize to the global scholarly community. We define a journal Usage Impact Factor which mimics the definition of the Thomson Scientific's ISI Impact Factor. Usage Impact Factor rankings are calculated on the basis of a large-scale usage data set recorded for the California State University system from 2003 to 2005. The resulting journal rankings are then compared to Thomson Scientific's ISI Impact Factor which is used as a baseline indicator of general impact. Our results indicate that impact as derived from California State University usage reflects the particular scientific and demographic characteristics of its communities.


title: Nonlinear Estimators and Tail Bounds for Dimension Reduction in $l_1$ Using Cauchy Random Projections

abstract: For dimension reduction in $l_1$, the method of {\em Cauchy random projections} multiplies the original data matrix $\mathbf{A} \in\mathbb{R}^{n\times D}$ with a random matrix $\mathbf{R} \in \mathbb{R}^{D\times k}$ ($k\ll\min(n,D)$) whose entries are i.i.d. samples of the standard Cauchy C(0,1). Because of the impossibility results, one can not hope to recover the pairwise $l_1$ distances in $\mathbf{A}$ from $\mathbf{B} = \mathbf{AR} \in \mathbb{R}^{n\times k}$, using linear estimators without incurring large errors. However, nonlinear estimators are still useful for certain applications in data stream computation, information retrieval, learning, and data mining. We propose three types of nonlinear estimators: the bias-corrected sample median estimator, the bias-corrected geometric mean estimator, and the bias-corrected maximum likelihood estimator. The sample median estimator and the geometric mean estimator are asymptotically (as $k\to \infty$) equivalent but the latter is more accurate at small $k$. We derive explicit tail bounds for the geometric mean estimator and establish an analog of the Johnson-Lindenstrauss (JL) lemma for dimension reduction in $l_1$, which is weaker than the classical JL lemma for dimension reduction in $l_2$. Asymptotically, both the sample median estimator and the geometric mean estimators are about 80% efficient compared to the maximum likelihood estimator (MLE). We analyze the moments of the MLE and propose approximating the distribution of the MLE by an inverse Gaussian.


title: Adaptation Knowledge Discovery from a Case Base

abstract: In case-based reasoning, the adaptation step depends in general on domain-dependent knowledge, which motivates studies on adaptation knowledge acquisition (AKA). CABAMAKA is an AKA system based on principles of knowledge discovery from databases. This system explores the variations within the case base to elicit adaptation knowledge. It has been successfully tested in an application of case-based decision support to breast cancer treatment.


title: A Genetic Algorithm Approach to the Grooming of Dynamic Traffic in Tree and Star Networks with Bifurcation

abstract: Traffic grooming is widely employed to reduce the number of ADM's and wavelengths. We consider the problem of grooming of dynamic traffic in WDM tree and star networks in this paper. To achieve better results, we used the bifurcation techniques to the grooming of arbitrary dynamic traffic in a strictly non-blocking manner in networks. Three splitting methods, including Traffic-Cutting, Traffic-Dividing and Synthesized-Splitting were proposed. A genetic algorithm (GA) approach based on these methods was proposed to tackle such grooming problems in tree and star networks. The performance of these algorithms was tested under different conditions in star and tree networks. Computer simulation results showed that our algorithm is efficient in reducing both the numbers of ADM's and wavelengths.


title: Considering users' behaviours in improving the responses of an information base

abstract: In this paper, our aim is to propose a model that helps in the efficient use of an information system by users, within the organization represented by the IS, in order to resolve their decisional problems. In other words we want to aid the user within an organization in obtaining the information that corresponds to his needs (informational needs that result from his decisional problems). This type of information system is what we refer to as economic intelligence system because of its support for economic intelligence processes of the organisation. Our assumption is that every EI process begins with the identification of the decisional problem which is translated into an informational need. This need is then translated into one or many information search problems (ISP). We also assumed that an ISP is expressed in terms of the user's expectations and that these expectations determine the activities or the behaviors of the user, when he/she uses an IS. The model we are proposing is used for the conception of the IS so that the process of retrieving of solution(s) or the responses given by the system to an ISP is based on these behaviours and correspond to the needs of the user.


title: Boolean Functions, Projection Operators and Quantum Error Correcting Codes

abstract: This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and non-additive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5,6,2)) code found by Rains [21]. It also extends to operator quantum error correcting codes.


title: A Non-Orthogonal Distributed Space-Time Coded Protocol Part II-Code Construction and DM-G Tradeoff

abstract: This is the second part of a two-part series of papers. In this paper, for the generalized non-orthogonal amplify and forward (GNAF) protocol presented in Part-I, a construction of a new family of distributed space-time codes based on Co-ordinate Interleaved Orthogonal Designs (CIOD) which result in reduced Maximum Likelihood (ML) decoding complexity at the destination is proposed. Further, it is established that the recently proposed Toeplitz space-time codes as well as space-time block codes (STBCs) from cyclic division algebras can be used in GNAF protocol. Finally, a lower bound on the optimal Diversity-Multiplexing Gain (DM-G) tradeoff for the GNAF protocol is established and it is shown that this bound approaches the transmit diversity bound asymptotically as the number of relays and the number of channels uses increases.


title: A Non-Orthogonal Distributed Space-Time Coded Protocol Part I: Signal Model and Design Criteria

abstract: In this two-part series of papers, a generalized non-orthogonal amplify and forward (GNAF) protocol which generalizes several known cooperative diversity protocols is proposed. Transmission in the GNAF protocol comprises of two phases - the broadcast phase and the cooperation phase. In the broadcast phase, the source broadcasts its information to the relays as well as the destination. In the cooperation phase, the source and the relays together transmit a space-time code in a distributed fashion. The GNAF protocol relaxes the constraints imposed by the protocol of Jing and Hassibi on the code structure. In Part-I of this paper, a code design criteria is obtained and it is shown that the GNAF protocol is delay efficient and coding gain efficient as well. Moreover GNAF protocol enables the use of sphere decoders at the destination with a non-exponential Maximum likelihood (ML) decoding complexity. In Part-II, several low decoding complexity code constructions are studied and a lower bound on the Diversity-Multiplexing Gain tradeoff of the GNAF protocol is obtained.


title: Multigroup-Decodable STBCs from Clifford Algebras

abstract: A Space-Time Block Code (STBC) in $K$ symbols (variables) is called $g$-group decodable STBC if its maximum-likelihood decoding metric can be written as a sum of $g$ terms such that each term is a function of a subset of the $K$ variables and each variable appears in only one term. In this paper we provide a general structure of the weight matrices of multi-group decodable codes using Clifford algebras. Without assuming that the number of variables in each group to be the same, a method of explicitly constructing the weight matrices of full-diversity, delay-optimal $g$-group decodable codes is presented for arbitrary number of antennas. For the special case of $N_t=2^a$ we construct two subclass of codes: (i) A class of $2a$-group decodable codes with rate $\frac{a}{2^{(a-1)}}$, which is, equivalently, a class of Single-Symbol Decodable codes, (ii) A class of $(2a-2)$-group decodable with rate $\frac{(a-1)}{2^{(a-2)}}$, i.e., a class of Double-Symbol Decodable codes. Simulation results show that the DSD codes of this paper perform better than previously known Quasi-Orthogonal Designs.


title: A Taxonomy of Peer-to-Peer Based Complex Queries: a Grid perspective

abstract: Grid superscheduling requires support for efficient and scalable discovery of resources. Resource discovery activities involve searching for the appropriate resource types that match the user's job requirements. To accomplish this goal, a resource discovery system that supports the desired look-up operation is mandatory. Various kinds of solutions to this problem have been suggested, including the centralised and hierarchical information server approach. However, both of these approaches have serious limitations in regards to scalability, fault-tolerance and network congestion. To overcome these limitations, organising resource information using Peer-to-Peer (P2P) network model has been proposed. Existing approaches advocate an extension to structured P2P protocols, to support the Grid resource information system (GRIS). In this paper, we identify issues related to the design of such an efficient, scalable, fault-tolerant, consistent and practical GRIS system using a P2P network model. We compile these issues into various taxonomies in sections III and IV. Further, we look into existing works that apply P2P based network protocols to GRIS. We think that this taxonomy and its mapping to relevant systems would be useful for academic and industry based researchers who are engaged in the design of scalable Grid systems.


title: Complexity of Data Flow Analysis for Non-Separable Frameworks

abstract: The complexity of round robin method of intraprocedural data flow analysis is measured in number of iterations over the control flow graph. Existing complexity bounds realistically explain the complexity of only Bit-vector frameworks which are separable. In this paper we define the complexity bounds for non-separable frameworks by quantifying the interdependences among the data flow information of program entities using an Entity Dependence Graph.


title: Decentralized Failure Diagnosis of Stochastic Discrete Event Systems

abstract: Recently, the diagnosability of {\it stochastic discrete event systems} (SDESs) was investigated in the literature, and, the failure diagnosis considered was {\it centralized}. In this paper, we propose an approach to {\it decentralized} failure diagnosis of SDESs, where the stochastic system uses multiple local diagnosers to detect failures and each local diagnoser possesses its own information. In a way, the centralized failure diagnosis of SDESs can be viewed as a special case of the decentralized failure diagnosis presented in this paper with only one projection. The main contributions are as follows: (1) We formalize the notion of codiagnosability for stochastic automata, which means that a failure can be detected by at least one local stochastic diagnoser within a finite delay. (2) We construct a codiagnoser from a given stochastic automaton with multiple projections, and the codiagnoser associated with the local diagnosers is used to test codiagnosability condition of SDESs. (3) We deal with a number of basic properties of the codiagnoser. In particular, a necessary and sufficient condition for the codiagnosability of SDESs is presented. (4) We give a computing method in detail to check whether codiagnosability is violated. And (5) some examples are described to illustrate the applications of the codiagnosability and its computing method.