From searching text to querying XML streams

XML data is queried with a limited form of regular expressions, in a language called XPath. New XML stream processing applications, such as content-based routing or selective dissemination of information, require thousands or millions of XPath expressions to be evaluated simultaneously on the incoming XML stream at a high, sustained rate. In its simplest approximation, the XPath evaluation problem is analogous to the text search problem, in which one or several regular expressions need to be matched to a given text. At a finer level, it is related to the tree pattern matching problem. However, unlike the traditional setting, the number of regular expressions here is much larger, while the “text” is much shorter, since it corresponds to the depth of the XML stream. In this paper we examine techniques that have been proposed for XML stream processing and describe a few open problems.     

A polyhedral approach to the stability of a family of coalitions

Using polyhedral combinatorics and graph theory results, we study unstable families of coalitions and analyze the effect of adding players or deleting coalitions in order to obtain a stable family. We also generalize the definitions and results to the case of fractional participation of players in coalitions.     

An equivalence to the Gleason problem

In this article we study the Gleason problem locally. A new method for solving the Gleason A problem is presented. This is done by showing an equivalent statement to the Gleason A problem. In order to prove this statement, necessary and a sufficient conditions for a bounded domain to have the Gleason A property are found. Also an example of a bounded but not smoothly-bounded domain in Cn is given, which satisfies the sufficient condition at the origin, and hence has the Gleason A property there.     

Cooperative game theory approach to allocating benefits of horizontal cooperation

Logistics costs in general, and transportation costs in particular, represent a large fraction of the operating costs of many companies. One way to try to reduce these costs is through horizontal cooperation among shippers. Thus, when the transportation needs of two or more companies are merged, their collective transportation requirements can be met at lower cost. The attainable cost savings are due to economies of scale, which translate into cheaper rates due to increased negotiation power, use of larger vehicles and bundling of shipments. In this paper, a linear model is presented and used to study the cost savings that different companies may achieve when they merge their transportation requirements. On the one hand, solving this optimization model for different collaboration scenarios allows testing and quantifying the synergies among different potential partners, thus identifying the most profitable collaboration opportunities. On the other, the problem of allocating the joint cost savings of the cooperation is tackled using cooperative game theory. The proposed approach is illustrated with an example in which different cooperative game solution concepts are compared. Extensive numerical experiments have also been carried out to gain insight into the properties of the corresponding cost savings game and the behavior of the different solution concepts.     

An interdisciplinary approach to coalition formation

A stable government is by definition not dominated by any other government. However, it may happen that all governments are dominated. In graph–theoretic terms this means that the dominance graph does not possess a source. In this paper we are able to deal with this case by a clever combination of notions from different fields, such as relational algebra, graph theory and social choice theory, and by using the computer support system RelView for computing solutions and visualizing the results. Using relational algorithms, in such a case we break all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set. In this way we can choose a government that is as close as possible to being un-dominated. To achieve unique solutions, we additionally apply the majority ranking recently introduced by Balinski and Laraki. The main parts of our procedure can be executed using the RelView tool. Its sophisticated implementation of relations allows to deal with graph sizes that are sufficient for practical applications of coalition formation.     

公共物品私人供给的纳什均衡分析

按私人供给的决定方式,公共物品可以划分为三类,替代型、互补型和包含型。本采用博弈论的方法,通过模型对三种情况下参与方的供给决策行为进行分析,并求出纳什均衡解,章最后讨论了所求解的合理性,并通过比较提出了一些有益的结论和启示。     

An approach to infinitary temporal proof theory

Aim of this work is to investigate from a proof-theoretic viewpoint a propositional and a predicate sequent calculus with an –type schema of inference that naturally interpret the propositional and the predicate until–free fragments of Linear Time Logic LTL respectively. The two calculi are based on a natural extension of ordinary sequents and of standard modal rules. We examine the pure propositional case (no extralogical axioms), the propositional and the first order predicate cases (both with a possibly infinite set of extralogical axioms). For each system we provide a syntactic proof of cut elimination and a proof of completeness.Supported by MIUR COFIN 02 Teoria dei Modelli e Teoria degli Insiemi, loro interazioni ed applicazioni.Supported by MIUR COFIN 02 PROTOCOLLO.Mathematics Subject Classification (2000):03B22, 03B45, 03F05     

An algorithm to analyze stability of gene-expression patterns

Many problems in the field of computational biology consist of the analysis of so-called gene-expression data. The successful application of approximation and optimization techniques, dynamical systems, algorithms and the utilization of the underlying combinatorial structures lead to a better understanding in that field. For the concrete example of gene-expression data we extend an algorithm, which exploits discrete information. This is lying in extremal points of polyhedra, which grow step by step, up to a possible stopping.We study gene-expression data in time, mathematically model it by a time-continuous system, and time-discretize this system. By our algorithm we compute the regions of stability and instability. We give a motivating introduction from genetics, present biological and mathematical interpretations of (in)stability, point out structural frontiers and give an outlook to future research.     

A new approach to the core and Weber set of multichoice games

Multichoice games have been introduced by Hsiao and Raghavan as a generalization of classical cooperative games. An important notion in cooperative game theory is the core of the game, as it contains the rational imputations for players. We propose two definitions for the core of a multichoice game, the first one is called the precore and is a direct generalization of the classical definition. We show that the precore coincides with the definition proposed by Faigle, and that the set of imputations may be unbounded, which makes its application questionable. A second definition is proposed, imposing normalization at each level, causing the core to be a convex compact set. We study its properties, introducing balancedness and marginal worth vectors, and defining the Weber set and the pre-Weber set. We show that the classical properties of inclusion of the (pre)core into the (pre)-Weber set as well as their coincidence in the convex case remain valid. A last section makes a comparison with the core defined by Van den Nouweland et al. A preliminary and short version of this paper has been presented at 4th Logic, Game Theory and Social Choice meeting, Caen, France, June 2005 (Xie and Grabisch 2005).     

A symbolic finite-state approach for automated proving of theorems in combinatorial game theory

We develop a finite-state automata approach, implemented in a Maple package Toads and Frogs available from our websites, for conjecturing, and then rigorously proving, values for large families of positions in Richard Guy's combinatorial game ‘Toads and Frogs’. In particular, we prove a conjecture of Jeff Erickson.     

Using algorithmic thinking to design algorithms: The case of critical path analysis

Algorithmic thinking is emerging as an important competence in mathematics education, yet research appears to be lagging this shift in curricular focus. The aim of this generative study is to examine how students use the cognitive skills of algorithmic thinking to design algorithms. Task-based interviews were conducted with four pairs of Year 12 students (n = 8) to analyze how they used decomposition and abstraction to specify the projects, designed algorithms to solve scheduling problems by first devising fundamental operations and then using algorithmic concepts to account for complex and special cases of the problems, and tested and debugged their algorithms. A deductive-inductive analytical process was used to classify students’ responses according to the four cognitive skills to develop sets of subskills to describe how the students engaged these cognitive skills.     

An algebraic analysis approach to linear time-varying systems

^** Email: zerz{at}mathematik.uni-kl.de This paper introduces an algebraic analysis approach to lineartime-varying systems. The analysis is carried out in an ‘almosteverywhere’ setting, i.e. the considered signals are smoothexcept for a set of measure zero, and the coefficients of thelinear ordinary differential equations are supposed to be rationalor meromorphic functions. The methodology is based on a normalform for matrices over the resulting ring of differential operators,which is a non-commutative analogue of the Smith form. Thisis used to establish a duality between linear time-varying systemson the one hand and modules over the ring of differential operatorson the other. This correspondence is based on the fact thatthe signal space is an injective cogenerator when consideredas a module over this ring of differential operators.     

Lie symmetries and exact solutions of variable coefficient mKdV equations: An equivalence based approach

Group classification of classes of mKdV-like equations with time-dependent coefficients is carried out. The usage of equivalence transformations appears to be a crucial point for the exhaustive solution of the problem. We prove that all the classes under consideration are normalized. This allows us to formulate the classification results in three ways: up to two kinds of equivalence (which are generated by transformations from the corresponding equivalence groups and all admissible point transformations) and using no equivalence. A simple way for the construction of exact solutions of mKdV-like equations using equivalence transformations is described.