Hierarchical sets in mathematical programming modeling languages

The mathematical notation commonly applied for the formulation of mathematical programming models is extended to include hierarchical structures. The proposed notation is related to hierarchical set concepts in the languages UIMP, AMPL, and LPL. With the proposed notation it is possible to aggregate and disaggregate over hierarchical structures. In addition, views are introduced to permit the use of hierarchical substructures and to create new hierarchies out of existing ones. The proposed notation for hierarchical sets and views is illustrated by applying it to the representation and estimation of social accounting matrices (SAMs).     

广义模糊传递性和形式三传递模糊矩阵

提出广义模糊传递性和形式三传递阵的概念，给出已有模糊传递定义的一种统一形式，确定所有的三传递模糊矩阵，初步理清它们的层次和部分等价关系，为模糊矩阵传递性进一步研究和应用提供背景和方法。     

Piecewise testable languages via combinatorics on words

A regular language L over an alphabet A is called piecewise testable if it is a finite Boolean combination of languages of the form A^∗a₁A^∗a₂A^∗…A^∗a_?A^∗, where a₁,…,a_?∈A, ?≥0. An effective characterization of piecewise testable languages was given in 1972 by Simon who proved that a language L is piecewise testable if and only if its syntactic monoid is J-trivial. Nowadays, there exist several proofs of this result based on various methods from algebraic theory of regular languages. Our contribution adds a new purely combinatorial proof.     

Analytical Formulation of the Classical Friction Model for Motion Analysis and Simulation

Starting from a precise definition of friction torque when velocity vanishes that distinguishes the case of instantaneous zero crossing from that where the velocity is zero over a time interval, this paper proposes a compact analytical formulation of the classical discontinuous friction model that is useful for motion analysis. A finite state machine that allows a numerically robust computation of motion equations when velocity vanishes or motion restarts is then defined. Simulation results show that the discontinuous model can be seen as an asymptotic approximation, infinitely fast, of a recently proposed continuous, dynamic friction model.     

Regular expression searching on compressed text

We present a solution to the problem of regular expression searching on compressed text. The format we choose is the Ziv–Lempel family, specifically the LZ78 and LZW variants. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text in O(2^m+mn+Rmlogm) worst case time. On average this drops to O(m²+(n+Rm)logm) or O(m²+n+Ru/n) for most regular expressions. This is the first nontrivial result for this problem. The experimental results show that our compressed search algorithm needs half the time necessary for decompression plus searching, which is currently the only alternative.     

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.     

Interactive error correction in implicative theories

Errors in implicative theories coming from binary data are studied. First, two classes of errors that may affect implicative theories are singled out. Two approaches for finding errors of these classes are proposed, both of them based on methods of Formal Concept Analysis. The first approach uses the cardinality minimal (canonical or Duquenne–Guigues) implication base. The construction of such a base is computationally intractable. Using an alternative approach one checks possible errors on the fly in polynomial time via computing closures of subsets of attributes. Both approaches are interactive, based on questions about the validity of certain implications. Results of computer experiments are presented and discussed.