Discovering Frequent Closed Partial Orders from Strings

Mining knowledge about ordering from sequence data is an important problem with many applications, such as bioinformatics, Web mining, network management, and intrusion detection. For example, if many customers follow a partial order in their purchases of a series of products, the partial order can be used to predict other related customers' future purchases and develop marketing campaigns. Moreover, some biological sequences (e.g., microarray data) can be clustered based on the partial orders shared by the sequences. Given a set of items, a total order of a subset of items can be represented as a string. A string database is a multiset of strings. In this paper, we identify a novel problem of mining frequent closed partial orders from strings. Frequent closed partial orders capture the nonredundant and interesting ordering information from string databases. Importantly, mining frequent closed partial orders can discover meaningful knowledge that cannot be disclosed by previous data mining techniques. However, the problem of mining frequent closed partial orders is challenging. To tackle the problem, we develop Frecpo (for frequent closed partial order), a practically efficient algorithm for mining the complete set of frequent closed partial orders from large string databases. Several interesting pruning techniques are devised to speed up the search. We report an extensive performance study on both real data sets and synthetic data sets to illustrate the effectiveness and the efficiency of our approach     

Admissible orders of typical hesitant fuzzy elements and their application in ordered information fusion in multi-criteria decision making

Typical hesitant fuzzy elements (HFEs) are quite useful for multi-criteria decision making (MCDM) in hesitant fuzzy setting. To reach a decision, it is necessary to derive the orders of HFEs. However, all the existing orders presented for HFEs in the literature are partial orders. We may need total orders sometimes such as in the situations when aggregating information by the ordered weighted aggregation (OWA) operators. Thus, the first purpose of this paper is to develop the total orders (called admissible orders) of HFEs for MCDM. The admissible orders improve the existing partial orders of HFEs and can be generated by a set of special functions. We demonstrate that the distinct ranking of HFEs can be derived according to different admissible orders. Another purpose is to redefine the hesitant fuzzy OWA operator based on the proposed total orders. Some interesting properties of the operator are also discussed.     

Convex cone-based partial order for multiple criteria alternatives

In this paper, we consider the problem of finding a preference-based strict partial order for a finite set of multiple criteria alternatives. We develop an approach based on information provided by the decision maker in the form of pairwise comparisons. We assume that the decision maker's value function is not explicitly known, but it has a quasi-concave form. Based on this assumption, we construct convex cones providing additional preference information to partially order the set of alternatives. We also extend the information obtained from the quasi-concavity of the value function to derive heuristic information that enriches the strict partial order. This approach can as such be used to partially rank multiple criteria alternatives and as a supplementary method to incorporate preference information in, e.g. Data Envelopment Analysis and Evolutionary Multi-Objective Optimization.     

Characterizing Communication Channel Deadlocks in Sequence Diagrams

UML sequence diagrams (SDs) are a mainstay of requirements specifications for communication protocols. Mauw and Reniers' algebraic (MRA) semantics formally specifies a behavior for these SDs that guarantees deadlock-free processes. Practitioners commonly use communication semantics that differ from MRA, which may result in deadlocks, for example, FIFO, token ring, etc. We define a process algebra that is an extension of the MRA semantics for regular SDs. Our algebra can describe several commonly used communication semantics. Regular SDs are constructed from concurrent message flows via iteration, branching, and sequential composition. Their behavior is defined in terms of a set of partial orders on the events in the SD. Such partial orders are known as causal orders. We define partial order theoretic properties of a causal order that are particular kinds of race condition. We prove that any of the common communication semantics that we list either guarantees deadlock-free SDs or can result in a deadlock if and only if a causal order of an SD contains one of these types of race condition. This describes a complete classification of deadlocks as specific types of race condition.     

Supporting ranking queries on uncertain and incomplete data

Large databases with uncertain information are becoming more common in many applications including data integration, location tracking, and Web search. In these applications, ranking records with uncertain attributes introduces new problems that are fundamentally different from conventional ranking. Specifically, uncertainty in records’ scores induces a partial order over records, as opposed to the total order that is assumed in the conventional ranking settings. In this paper, we present a new probabilistic model, based on partial orders, to encapsulate the space of possible rankings originating from score uncertainty. Under this model, we formulate several ranking query types with different semantics. We describe and analyze a set of efficient query evaluation algorithms. We show that our techniques can be used to solve the problem of rank aggregation in partial orders under two widely adopted distance metrics. In addition, we design sampling techniques based on Markov chains to compute approximate query answers. Our experimental evaluation uses both real and synthetic data. The experimental study demonstrates the efficiency and effectiveness of our techniques under various configurations.     

A New Discriminant Principal Component Analysis Method with Partial Supervision

Principal component analysis (PCA) is one of the most widely used unsupervised dimensionality reduction methods in pattern recognition. It preserves the global covariance structure of data when labels of data are not available. However, in many practical applications, besides the large amount of unlabeled data, it is also possible to obtain partial supervision such as a few labeled data and pairwise constraints, which contain much more valuable information for discrimination than unlabeled data. Unfortunately, PCA cannot utilize that useful discriminant information effectively. On the other hand, traditional supervised dimensionality reduction methods such as linear discriminant analysis perform on only labeled data. When labeled data are insufficient, their performances will deteriorate. In this paper, we propose a novel discriminant PCA (DPCA) model to boost the discriminant power of PCA when both unlabeled and labeled data as well as pairwise constraints are available. The derived DPCA algorithm is efficient and has a closed form solution. Experimental results on several UCI and face data sets show that DPCA is superior to several established dimensionality reduction methods.     

On the partial stochastic realization problem

We describe a complete parameterization of the solutions to the partial stochastic realization problem in terms of a nonstandard matrix Riccati equation. Our analysis of this covariance extension equation (CEE) is based on a complete parameterization of all strictly positive real solutions to the rational covariance extension problem, answering a conjecture due to Georgiou (1987) in the affirmative. We also compute the dimension of partial stochastic realizations in terms of the rank of the unique positive semidefinite solution to the CEE, yielding some insights into the structure of solutions to the minimal partial stochastic realization problem. By combining this parameterization with some of the classical approaches in partial realization theory, we are able to derive new existence and robustness results concerning the degrees of minimal stochastic partial realizations. As a corollary to these results, we note that, in sharp contrast with the deterministic case, there is no generic value of the degree of a minimal stochastic realization of partial covariance sequences of fixed length     

An Expressively Complete Linear Time Temporal Logic for Mazurkiewicz Traces

A basic result concerning LTL, the propositional temporal logic of linear time, is that it is expressively complete; it is equal in expressive power to the first order theory of sequences. We present here a smooth extension of this result to the class of partial orders known as Mazurkiewicz traces. These partial orders arise in a variety of contexts in concurrency theory and they provide the conceptual basis for many of the partial order reduction methods that have been developed in connection with LTL-specifications.We show that LTrL, our linear time temporal logic, is equal in expressive power to the first order theory of traces when interpreted over (finite and) infinite traces. This result fills a prominent gap in the existing logical theory of infinite traces. LTrL also constitutes a characterisation of the so-called trace consistent (robust) LTL-specifications. These are specifications expressed as LTL formulas that do not distinguish between different linearisations of the same trace and hence are amenable to partial order reduction methods.     

A token based distributed algorithm for supporting mutual exclusion in opportunistic networks

Opportunistic networks are essentially distributed networks with transient connectivity among nodes. Nodes in opportunistic networks are resource constrained, mobile and opportunistically come in contact with each other. In such a distributed network, nodes may require exclusive access to a shared object or resource. Ensuring freedom from starvation is a challenging problem in opportunistic networks due to limited pairwise connectivity and node failures. In this paper, we review mutual exclusion algorithms proposed for generic mobile ad hoc networks (MANETs) and discuss their applicability to opportunistic networks. Further, we propose a novel token based algorithm¹ and prove its correctness. Simulation results show that our algorithm is communication efficient as compared to other algorithms proposed for generic mobile ad hoc networks. We also propose a timeout based fault detection algorithm that exploits the intercontact time distributions.     

Probabilistic opacity for Markov decision processes

Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministic choice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaque becomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.     

Metric semantics from partial order semantics

In dealing with denotational semantics of programming languages partial orders resp. metric spaces have been used with great benefit in order to provide a meaning to recursive and repetitive constructs. This paper presents two methods to define a metric on a subset of a complete partial order such that is a complete metric spaces and the metric semantics on coincides with the partial order semantics on when the same semantic operators are used. The first method is to add a ‘length’ on a complete partial order which means a function of increasing power. The second is based on the ideas of [11] and uses pseudo rank orderings, i.e. monotone sequences of monotone functions . We show that SFP domains can be characterized as special kinds of rank orderded cpo's. We also discuss the connection between the Lawson topology and the topology induced by the metric. Received 11 July 1995 / 1 August 1996     

Spatial PID consensus controllers for distributed filters of distributed parameter systems

This paper considers the spatial penalization of the pairwise state estimate differences as used to enforce consensus in spatially distributed filters. A spatially distributed process, described by a parabolic partial differential equation is assumed to have a network of in-domain sensors. Each spatially distributed filter corresponds to a single sensor in the network and the goal is for these filters to collaboratively reach a consensus on the process state estimate. To enhance the agreement of the spatially distributed filters, the spatial gradient of the pairwise difference of state estimates is used as a means to penalize their disagreement. Additionally, a proportional and an integral penalization of the pairwise differences are also examined in order to produce a spatial proportional–integral–derivative penalization. To address the partial connectivity, certain conditions on the communication topology are given implicitly in terms of the inner product of the state estimation errors and their pairwise differences. Simulation studies provide an insight on the effects of this spatial penalizations.     

一种半监督的局部扩展式重叠社区发现方法

重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想,不仅利用网络的拓扑结构信息,还充分地利用网络节点的属性信息.首先将网络节点的属性信息转化为成对约束,并根据成对约束修正网络的拓扑结构,使网络中的社区结构更加明显;然后基于网络节点的度中心性选取种子节点,得到分散的、局部节点度大的种子作为初始社区;再采用贪心策略将初始社区向邻居节点扩展,得到局部连接紧密的社区;最后检测并合并冗余社区,得到高覆盖率的社区发现结果.在模拟网络数据和真实网络数据上与当前有代表性的基于局部扩展的重叠社区发现算法进行了对比实验,结果表明SLEM方法在稀疏程度不同的网络上均能发现较高质量的重叠社区结构.     

Specifying and Automatically Generating a Specialization Tool for Fortran 90

Partial evaluation is an optimization technique traditionally used in compilation. We have adapted this technique to the understanding of scientific application programs during their maintenance. We have implemented a tool that analyzes Fortran 90 application programs and performs an interprocedural pointer analysis. This paper presents a dynamic semantics of Fortran 90 and manually derives a partial evaluator from this semantics. The tool implementing the specifications is also detailed. The partial evaluator has been implemented in a generic programming environment and a graphical interface has been developed to visualize the information computed during the partial evaluation (values of variables, already analyzed procedures, scope of variables, removed statements, etc.).     

Interval-Valued Finite Markov Chains

The requirement that precise state and transition probabilities be available is often not realistic because of cost, technical difficulties or the uniqueness of the situation under study. Expert judgements, generic data, heterogeneous and partial information on the occurrences of events may be sources of the probability assessments. All this source information cannot produce precise probabilities of interest without having to introduce drastic assumptions often of quite an arbitrary nature. in this paper the theory of interval-valued coherent previsions is employed to generalise discrete Markov chains to interval-valued probabilities. A general procedure of interval-valued probability elicitation is analysed as well. In addition, examples are provided.     

Fixed-point constructions in order-enriched categories

The fixed-point construction of Scott, giving a continuous lattice solution of equations X ? T(X) where T is an endofunctor on the category of continuous lattices, is extended to categories enriched by partial orderings on the morphism sets. The result allows data structures to be realized not only in the category of continuous lattices, but also in the category of complete lattices, in the category of complete partial orders, or in any of several related categories of partial orders.     

Compact and efficiently verifiable models for concurrent systems

Partial orders are a fundamental mathematical structure capable of representing concurrency and causality on a set of atomic events. In many applications it is essential to consider multiple partial orders, each representing a particular behavioral scenario or an operating mode of a system. With the exploding growth of the complexity of systems that software and hardware engineers design today, it is no longer feasible to represent each partial order of a large system explicitly, therefore compressed representations of sets of partial orders become essential for improving the scalability of design automation tools. In this paper we study two well known mathematical formalisms capable of the compressed representation of sets of partial orders: Labeled Event Structures and Conditional Partial Order Graphs. We discuss their advantages and disadvantages and propose efficient algorithms for transforming a set of partial orders from a given compressed representation in one formalism into an equivalent representation in another formalism without explicitly enumerating every partial order. The proposed algorithms make use of an intermediate mathematical formalism which we call Conditional Labeled Event Structures that combines the advantages of both structures. Finally, we compare these structures on a number of benchmarks coming from concurrent software and hardware domains.     

Relating axiomatic and operational semantics of place/transition nets: From process terms to partial orders

In this paper we define partial orders associated to process terms of place/transition nets. Further, we construct a set of partial orders from a given set of process terms. For place/transition nets without loops we prove the following result:The set of minimal partial orders constructed from process terms is in a one-to-one correspondence with the set of minimal partial orders defined by processes of the given net.