Can Finite Samples Detect Singularities of Real-Valued Functions?

Commonly, in learning theory, the task of the learner is to identify an unknown target object. We consider a variant of this basic task in which the learner is required only to decide whether the unknown target has a certain property. We allow an infinite learning process in which the learner is required to eventually arrive at the correct answer. We say that a problem for which such a learning algorithm exists is Decidable In the Limit (DIL). We analyze the class of DIL problems and provide a necessary and sufficient condition for the membership of a decision problem in this class. We offer an algorithm for any DIL problem, and apply it to several types of learning tasks. We introduce an extension of the usual Inductive Inference learning model—Inductive Inference with a Cheating Teacher. In this model the teacher may choose to present to the learner, not only a language belonging to the agreed-upon family of languages, but also an arbitrary language outside this family. In such a case we require that the learner will be able to eventually detect the faulty choice made by the teacher. We show that such a strong type of learning is possible, and there exist learning algorithms that will fail only on arbitrarily small sets of faulty languages. Furthermore, if an a priori probability distribution P , according to which f is being chosen, is available to the algorithm, then it can be strengthened into a finite algorithm. More precisely, for many distributions P , there exists a polynomial function, l , such that, for every 0 < δ < 1 , there is an algorithm using at most l(log(δ)) many probes that succeeds on more than (1-δ) of the f 's (as measured by P ). We believe that the new approach presented here will be found useful for many further applications. Received February 14, 1997; revised July 6, 1997, and July 18, 1997.     

A unified approach to modelling the performance of concurrent systems

Quantitative design is crucial to ICT and it is therefore important to integrate performance modelling techniques into support environments that facilitate the correct construction of computer systems. We consider Performance Modelling Interchange Formats (PMIFs), which allow models to be specified in a uniform way and ported to a number of tools that solve them. We focus on extending the class of models describable in a PMIF that can be solved analytically – specifically, yielding a product-form solution for their equilibrium state probabilities. We use an extension of an established theorem, called the ‘reversed compound agent theorem’ (RCAT) as the basis of the analytical modelling tool into which the extended PMIF feeds models. We describe the RCAT methodology in practical terms, how it is integrated into an extended PMIF, and illustrate our methodology with three examples.     

Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs

We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An element means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is APX-hard when there are only three terminal nodes, thus answering an open question. Our main focus is on the special case when the graph is planar. We show that the problem of finding two element-disjoint Steiner trees in a planar graph is NP-hard. Similarly, the problem of finding two edge-disjoint Steiner trees in a planar graph is NP-hard. We design an algorithm for planar graphs that achieves an approximation guarantee close to 2. In fact, given a planar graph that is k element-connected on the terminals (k is an upper bound on the number of element-disjoint Steiner trees), the algorithm returns $\lfloor\frac{k}{2} \rfloor-1$ element-disjoint Steiner trees. Using this algorithm, we get an approximation algorithm for the edge-disjoint version of the problem on planar graphs that improves on the previous approximation guarantees. We also show that the natural LP relaxation of the planar problem has an integrality ratio approaching?2.     

Distributed inversion in timed discrete event systems

We consider a discrete event system (DES) modeled by a timed automaton with partial state and event observations. We view the system as an input-output system, where the input is a sequence of event lifetimes, and the output is the resulting sequence of events, states, and transition epochs. We consider the problem of extracting event lifetimes (input) from observations of the output trajectory, which we callinversion. We give necessary and sufficient conditions forinvertibility, and an algorithm that extracts event lifetimes from any given output observation of an invertible system. We describe a distributed timed DES model based on the prioritized synchronous product of subsystems, and study the inversion problem in this framework. We show that invertibility in the subsystems implies invertibility in the global system. To illustrate our results, we provide an example of a tandem network.     

Efficient algorithms for segmentation of item-set time series

We propose a special type of time series, which we call an item-set time series, to facilitate the temporal analysis of software version histories, email logs, stock market data, etc. In an item-set time series, each observed data value is a set of discrete items. We formalize the concept of an item-set time series and present efficient algorithms for segmenting a given item-set time series. Segmentation of a time series partitions the time series into a sequence of segments where each segment is constructed by combining consecutive time points of the time series. Each segment is associated with an item set that is computed from the item sets of the time points in that segment, using a function which we call a measure function. We then define a concept called the segment difference, which measures the difference between the item set of a segment and the item sets of the time points in that segment. The segment difference values are required to construct an optimal segmentation of the time series. We describe novel and efficient algorithms to compute segment difference values for each of the measure functions described in the paper. We outline a dynamic programming based scheme to construct an optimal segmentation of the given item-set time series. We use the item-set time series segmentation techniques to analyze the temporal content of three different data sets–Enron email, stock market data, and a synthetic data set. The experimental results show that an optimal segmentation of item-set time series data captures much more temporal content than a segmentation constructed based on the number of time points in each segment, without examining the item set data at the time points, and can be used to analyze different types of temporal data.     

Application-independent evaluation of speaker detection

We propose and motivate an alternative to the traditional error-based or cost-based evaluation metrics for the goodness of speaker detection performance. The metric that we propose is an information-theoretic one, which measures the effective amount of information that the speaker detector delivers to the user. We show that this metric is appropriate for the evaluation of what we call application-independent detectors, which output soft decisions in the form of log-likelihood-ratios, rather than hard decisions. The proposed metric is constructed via analysis and generalization of cost-based evaluation metrics. This construction forms an interpretation of this metric as an expected cost, or as a total error-rate, over a range of different application-types. We further show how the metric can be decomposed into a discrimination and a calibration component. We conclude with an experimental demonstration of the proposed technique to evaluate three speaker detection systems submitted to the NIST 2004 Speaker Recognition Evaluation.     

On Minimizing the Cost of Location Management in Mobile Environments

A mobile host typically has a home agent that maintains a registry of its current location. This registry is normally updated every time a host changes its current network. The update cost could be reduced using a two-tier update process in which a registry is updated using special agents, called proxy agents. We study the problem of selecting proxy agents to minimize the cost of search associated with this two-tier update approach. We show that the problem can be formulated as p-center or p-median finding problems. We focus on the p-center formulation. Due to the intractability of the problem, we introduce a distributed strategy to solve the general problem and show that it yields an approximate solution for arbitrary networks. We present an implementation of the distributed strategy that produces an optimal solution for ring networks. We prove that the optimal solution for rings is fault tolerant and resilient to topology changes.     

关于无个人公钥的群认证

群认证是一种多方认证机制,研究动态群的成员们如何确认每个成员身份的真实性。这里,群组成员没有个人公钥。本文首先分析了Harn的群认证方案,证明他的方案在有意义的参数下是不安全的。我们还研究了群认证和几个多方签名之间的关系。我们证明基于身份的多重签名可以转换为安全群认证协议,而门限签名方案没有这种特性。我们还证明,如果去掉签名消息的话,Bellare和Neven的基于ID的多重签名方案实际上就是一个安全的群认证协议。     

Sampling-based estimators for subset-based queries

We consider the problem of using sampling to estimate the result of an aggregation operation over a subset-based SQL query, where a subquery is correlated to an outer query by a NOT EXISTS, NOT IN, EXISTS or IN clause. We design an unbiased estimator for our query and prove that it is indeed unbiased. We then provide a second, biased estimator that makes use of the superpopulation concept from statistics to minimize the mean squared error of the resulting estimate. The two estimators are tested over an extensive set of experiments. Material in this paper is based upon work supported by the National Science Foundation via grants 0347408 and 0612170.     

On the induced matching problem

We study extremal questions on induced matchings in certain natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least n/40 while there are planar twinless graphs that do not contain an induced matching of size (n+10)/27. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most 40k that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time O(k⁹¹+n) whether a planar graph contains an induced matching of size at least k.     

Nash Stability in Additively Separable Hedonic Games and Community Structures

We prove that the problem of deciding whether a Nash stable partition exists in an Additively Separable Hedonic Game is NP-complete. We also show that the problem of deciding whether a non trivial Nash stable partition exists in an Additively Separable Hedonic Game with non-negative and symmetric preferences is NP-complete. We motivate our study of the computational complexity by linking Nash stable partitions in Additively Separable Hedonic Games to community structures in networks. Our results formally justify that computing community structures in general is hard. The research is partly sponsored by the company Cofman ().     

On ontology-driven document clustering using core semantic features

Incorporating semantic knowledge from an ontology into document clustering is an important but challenging problem. While numerous methods have been developed, the value of using such an ontology is still not clear. We show in this paper that an ontology can be used to greatly reduce the number of features needed to do document clustering. Our hypothesis is that polysemous and synonymous nouns are both relatively prevalent and fundamentally important for document cluster formation. We show that nouns can be efficiently identified in documents and that this alone provides improved clustering. We next show the importance of the polysemous and synonymous nouns in clustering and develop a unique approach that allows us to measure the information gain in disambiguating these nouns in an unsupervised learning setting. In so doing, we can identify a core subset of semantic features that represent a text corpus. Empirical results show that by using core semantic features for clustering, one can reduce the number of features by 90% or more and still produce clusters that capture the main themes in a text corpus.     

Efficient query evaluation on probabilistic databases

We describe a framework for supporting arbitrarily complex SQL queries with “uncertain” predicates. The query semantics is based on a probabilistic model and the results are ranked, much like in Information Retrieval. Our main focus is query evaluation. We describe an optimization algorithm that can compute efficiently most queries. We show, however, that the data complexity of some queries is #P-complete, which implies that these queries do not admit any efficient evaluation methods. For these queries we describe both an approximation algorithm and a Monte-Carlo simulation algorithm.     

t-Norm based cuts of intuitionistic fuzzy sets

We consider the system of intuitionistic fuzzy sets (IF-sets) in a universe X and study the cuts of an IF-set. Suppose a left continuous triangular norm is given. The t-norm based cut (level set) of an IF-set is defined in a way that binds the membership and nonmembership functions via the triangular norm. This is an extension of usual cuts of IF-sets. We show that the system of these cuts fulfils analogical properties as usual systems of cuts. However, it is not possible to reconstruct an IF-set from the system of t-norm based cuts.     

The use of mTags for mandatory security: a case study

mTags is an efficient mechanism that augments inter‐thread messages with lightweight metadata. We introduce and discuss a case study that we have conducted in the use of mTags for realizing a kind of mandatory security. Although mTags can be implemented for any message passing thread‐based system, we consider an implementation of it in the POSIX‐compliant QNX Neutrino, a commercial microkernel‐based system. The approach to mandatory security that we adopt is Usable Mandatory Integrity Protection, which has been proposed in recent research. We call our adaptation of Usable Mandatory Integrity Protection using mTags, μMIP. We discuss the challenges we faced, and our design and implementation that overcomes these challenges. We discuss the performance of our implementation for well‐established benchmarks. We conclude with the observation that mTags can be useful and practical to realize mandatory security in realistic systems. Copyright © 2013 John Wiley & Sons, Ltd.     

Power Assignment in Radio Networks with Two Power Levels

We study the power-assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges—short and long. We show that this problem is NP-hard, and we present an O(n²)-time assignment algorithm such that the number of transmitters that are assigned long range by the algorithm is at most (11/6) times the number of transmitters that are assigned long range by an optimal algorithm. We also present a (9/5)-approximation algorithm for this problem whose running time is considerably higher.     

Differencing and merging of architectural views

Differencing and merging architectural views is an important activity in software engineering. However, existing approaches are still based on restrictive assumptions, such as requiring view elements to have unique identifiers or exactly matching types, which is often not the case in many application domains. We propose an approach based on structural information. We generalize a published polynomial-time tree-to-tree correction algorithm that detects inserts, renames and deletes, into a novel algorithm that additionally detects restricted moves. Our algorithm also supports forcing and preventing matches between view elements. We incorporate the algorithm into tools to compare and merge Component-and-Connector (C&C) architectural views. We provide an empirical evaluation of the algorithm. We illustrate the tools using extended examples, and use them to detect and reconcile interesting differences between real architectural views. This article is an expanded version of the following paper: Abi-Antoun, M., Aldrich, J., Nahas, N., Schmerl, B., and Garlan, D: 2006, ‘Differencing and Merging of Architectural Views’. In: Proceedings of the 21st IEEE International Conference on Automated Software Engineering, pp. 47–58.     

Optimizing insurance and reinsurance in the dynamic Cramér-Lundberg model

We find optimal (from the insurer’s point of view) strategies for insurance and reinsurance in a controllable Cramér-Lundberg risk process that describes the capital dynamics of an insurance company over an extended time interval. As the optimality criterion being minimized, we use the stationary variation coefficient, taking into account additional constraints on residual risks for both insurers and reinsurer. We establish that it is best to use stop-loss reinsurance with an upper limit and insurance which is a combination of a stop-loss strategy and franchise. We derive equations that define optimal strategy parameters.     

Optimal control of systems with a unitary semigroup and with colocated control and observation

We solve the quadratic optimal control problem on an infinite time interval for a class of linear systems whose state space is a Hilbert space and whose operator semigroup is unitary. The difficulty is that the systems in this class, having unbounded control and observation operators, may be ill-posed. We show that there is a surprisingly simple solution to the problem (the optimal feedback turns out to be output feedback). Our approach is to use a change of variables which transforms the system into a one which, according to recent research, is known to be conservative. We show that, under a mild assumption, the transfer function of this conservative system is inner, and then it follows that the optimal control of this conservative system is trivial. We give an example with the wave equation on an n-dimensional domain, with Neumann control and Dirichlet observation of the velocity.     

Exemplar queries: a new way of searching

Modern search engines employ advanced techniques that go beyond the structures that strictly satisfy the query conditions in an effort to better capture the user intentions. In this work, we introduce a novel query paradigm that considers a user query as an example of the data in which the user is interested. We call these queries exemplar queries. We provide a formal specification of their semantics and show that they are fundamentally different from notions like queries by example, approximate queries and related queries. We provide an implementation of these semantics for knowledge graphs and present an exact solution with a number of optimizations that improve performance without compromising the result quality. We study two different congruence relations, isomorphism and strong simulation, for identifying the answers to an exemplar query. We also provide an approximate solution that prunes the search space and achieves considerably better time performance with minimal or no impact on effectiveness. The effectiveness and efficiency of these solutions with synthetic and real datasets are experimentally evaluated, and the importance of exemplar queries in practice is illustrated.