On Binary Computation Structures

Based on a modification of Moss' and Parikh's topological modal language [8], we study a generalization of a weakly expressive fragment of a certain propositional modal logic of time. We define a bimodal logic comprising operators for knowledge and nexttime. These operators are interpreted in binary computation structures. We present an axiomatization of the set T of theorems valid for this class of semantical domains and prove – as the main result of this paper – its completeness. Moreover, the question of decidability of T is treated.     

Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.     

直径不超过4的树的割宽

§ 1　IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see [2 ] ) .We shall follow the graph-theoretic terminology and notation of [1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…     

Level of nodes in increasing trees revisited

Simply generated families of trees are described by the equation T(z) = ϕ(T(z)) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label ∈ { 1,…,n}, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ϕ(u) is just a polynomial). The random variable of interest is the level of the node (labelled) j, in random trees of size n ≥ j. For very simple families, this is independent of n, and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j,n → ∞ such that n − j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the covariance of the level sizes in random recursive trees

In this paper we study the covariance structure of the number of nodes k and l steps away from the root in random recursive trees. We give an analytic expression valid for all k, l and tree sizes N. The fraction of nodes k steps away from the root is a random probability distribution in k. The expression for the covariances allows us to show that the total variation distance between this (random) probability distribution and its mean converges in probability to zero. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 519–539, 2002     

Rigidity of Branch Groups Acting on Rooted Trees

Automorphisms of groups acting faithfully on rooted trees are studied. We find conditions under which every automorphism of such a group is induced by a conjugation from the full automorphism group of the rooted tree. These results are applied to known examples such as Grigorchuk groups, Gupta–Sidki group, etc.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Extension of multivariate regression trees to interval data. Application to electricity load profiling

Summary  Several data can be presented as interval curves where intervals reflect a within variability. In particular, this representation is well adapted for load profiles, which depict the electricity consumption of a class of customers. Electricity load profiling consists in assigning a daily load curve to a customer based on their characteristics such as energy requirement. Within the load profiling scope, this paper investigates the extension of multivariate regression trees to the case of interval dependent (or response) variables. The tree method aims at setting up simultaneously load profiles and their assignment rules based on independent variables. The extension of multivariate regression trees to interval responses is detailed and a global approach is defined. It consists in a first stage of a dimension reduction of the interval response variables. Thereafter, the extension of the tree method is applied to the first principal interval components. Outputs are the classes of the interval curves where each class is characterized both by an interval load profile (e.g. the class prototype) and an assignment rule based on the independent variables.     

Note on the application of the reduced graph model in conjunction with search trees to the enumeration ofKekulé structures

The reduced graph model, when used in conjunction with the search trees method, provides a novel combinatorial procedure for the enumeration and generation ofKekulé structures. The procedure is suited for large benzenoid hydrocarbons consisting of cata- and thin peri-condensed parts.

---

Zur Anwendung des Reduced Graph Model im Zusammenhang mit Search Trees zur Ermittlung der Anzahl möglicherKekulé-Strukturen

Zusammenfassung Das Modell erlaubt mit der im Titel genannten Kombination eine neuartige Methode zur Ermittlung und Generierung vonKekulé-Strukturen. Das Verfahren ist für große benzoide Kohlenwasserstoffe geeignet, die aus cata- und (dünnen) peri-kondensierten Teilstrukturen bestehen.