The longest common subsequence problem for arc-annotated sequences

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The

Full-size image

problem has recently been introduced in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures and present some new algorithmic and complexity results on the problem. Some of our results answer an open question in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] and some others improve the hardness results in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280].     

Some Problems with the Russellian Open Future

In a recently published paper, Todd (Mind, 125(499), pp. 775–798, 2016a) advocates a novel treatment of future contingents. On his view, all statements concerning the contingent future are false. He motivates his semantic postulates by considerations in philosophy of time and modality, in particular by the claim that there is no actual future. I present a number of highly controversial consequences of Todd’s theory. Inadequacy of his semantics might indirectly serve as an argument against the philosophical view underpinning his proposal.     

A Canonical Theory of Origins and Development of Social Complexity

The puzzle of origins and future of government and social complexity in human and social dynamics, arguably a characteristic feature of the emergence and long-term evolution of hierarchy and power in the history of civilizations, is an enduring topic that has challenged political scientists, anthropological archaeologists, and other social scientists and historians. This paper proposes a new computational theory for the emergence of social complexity that accounts for the earliest formation of systems of government (pristine polities) in prehistory and early antiquity, as well as present and future political development. This general social theory is based on a “fast process” of crisis and opportunistic decision-making through collective action, which feeds a “slow” process of political development or decay. The “fast” core iterative process is “canonical” in the sense that it undergoes variations on a recurring theme of signal detection, information-processing, problem-solving, successful adaptation and occasional failure. When a group is successful in managing or overcoming serious situational changes (stresses or opportunities, endogenous or exogenous, social or physical) a probabilistic phase transition may occur, under a specified set of conditions, yielding a long-term (slow) probabilistic accrual process of emergent sociopolitical complexity and development. A reverse process may account for decay. The canonical theory is being formally implemented through the “PoliGen” agent-based model (ABM), based on the new Multi-Agent Simulator of Networks and Neighborhoods (MASON). Empirically, the theory is testable with the datasets on polities developed by the Long-Range Analysis of War (LORANOW) Project. This paper focuses on the concepts, mechanisms, and basic formal structure that constitute the canonical theory and inform the subsequent simulation model.     

The wonderland of reflections

A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a fixed template is that pp-interpretations between at most countable ω-categorical relational structures have two algebraic counterparts for their polymorphism clones: a semantic one via the standard algebraic operators H, S, P, and a syntactic one via clone homomorphisms (capturing identities). We provide a similar characterization which incorporates all relational constructions relevant for CSPs, that is, homomorphic equivalence and adding singletons to cores in addition to ppinterpretations. For the semantic part we introduce a new construction, called reflection, and for the syntactic part we find an appropriate weakening of clone homomorphisms, called h1 clone homomorphisms (capturing identities of height 1).As a consequence, the complexity of the CSP of an at most countable ω-categorical structure depends only on the identities of height 1 satisfied in its polymorphism clone as well as the natural uniformity thereon. This allows us in turn to formulate a new elegant dichotomy conjecture for the CSPs of reducts of finitely bounded homogeneous structures.Finally, we reveal a close connection between h1 clone homomorphisms and the notion of compatibility with projections used in the study of the lattice of interpretability types of varieties.     

A Long-Step, Cutting Plane Algorithm for Linear and Convex Programming

A cutting plane method for linear programming is described. This method is an extension of Atkinson and Vaidya's algorithm, and uses the central trajectory. The logarithmic barrier function is used explicitly, motivated partly by the successful implementation of such algorithms. This makes it possible to maintain primal and dual iterates, thus allowing termination at will, instead of having to solve to completion. This algorithm has the same complexity (O(nL ²) iterations) as Atkinson and Vaidya's algorithm, but improves upon it in that it is a long-step version, while theirs is a short-step one in some sense. For this reason, this algorithm is computationally much more promising as well. This algorithm can be of use in solving combinatorial optimization problems with large numbers of constraints, such as the Traveling Salesman Problem.     

A generalization of a formula of Steiner

Summary Combinatorial formulae for the numbers of cells of subdivision, of varying dimensions, when hyperplanes in general position intersect an open convex set of ^d, are derived. They coincide with basic formulae for the probabilities of combinations of events. The dual result is stated.I should like to thank a referee for drawing attention to the duality.     

Combinatorial Proofs of Identities in Ramanujan’s Lost Notebook Associated with the Rogers-Fine Identity and False Theta Functions

Ramanujans lost notebook contains several identities arising from the Rogers-Fine identity and/or Rogers false theta functions. Combinatorial proofs for many of these identities are given.AMS Subject Classification: 05A17, 11P81.     

幂向量,复合向量数及其函数理论

本文提出向量为其幂向量和向量幂级数．向量幂级数由一实数和某一向量联合组成的“复合向量数”及其函数有重要涵义．这数也有运算法则．从复合向量数的函数理论分析知其函数有导数和解析函数的必要和充分条件．这些条件构成了“双曲型”方程的特征以及函数的积分性质等．     

Graphs With Least Eigenvalue —2: A New Proof of the 31 Forbidden Subgraphs Theorem

Generalized line graphs were introduced by Hoffman Proc. Calgary Internat. Conf. on Combinatorial Structures and their applications, Gordon and Breach, New York (1970); they were characterized in 1980 by a collection of 31 forbidden induced subgraphs, obtained independently by Cvetkovi et al., Comptes Rendus Math. Rep. Acad. Sci. Canada (1980) and S. B. Rao et al., Proc. Second Symp., Indian Statistical Institute, Calcutta, Lecture Notes in Math., (1981). Here a short new proof of this characterization theorem is given, based on an edge-colouring technique.     

On the Complexity of Partial Order Properties

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n ² for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k n ² / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.     

Problems, Models and Complexity. Part I: Theory

The meaning of the term problem in operations research (OR) deviates from the understanding in the theoretical computer sciences: While an OR problem is often conceived to be stated or represented by model formulations, a computer-science problem can be viewed as a mapping from encoded instances to solutions. Such a computer-science problem turns out to be rather similar to an OR model formulation. This ambiguity may cause difficulties if the computer-science theory of computational complexity is applied in the OR context. In OR, a specific model formulation is commonly used in the analysis of the underlying problem and the results obtained for this model are simply lifted to the problem level. But this may lead to erroneous results, if the model used is not appropriate for such an analysis of the problem.To resolve this issue, we first suggest a new precise formal definition of the term problem which is identified with an equivalence class of models describing it. Afterwards, a new definition is suggested for the size of a model which depends on the assumed encoding scheme. Only models which exhibit a minimal size with respect to a reasonable encoding scheme finally turn out to be suitable for the model-based complexity analysis of an OR problem. Therefore, the appropriate choice (or if necessary the construction) of a suitable representative of an OR problem becomes an important theoretical aspect of the modelling process.     

A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems

We improve the well-known result presented in Bertsimas and Sim (Math Program B98:49–71, 2003) regarding the computation of optimal solutions of Robust Combinatorial Optimization problems with interval uncertainty in the objective function coefficients. We also extend this improvement to a more general class of Combinatorial Optimization problems with interval uncertainty.     

Accessing complexity from genome information

This paper studies the information content of the chromosomes of 24 species. In a first phase, a scheme inspired in dynamical system state space representation is developed. For each chromosome the state space dynamical evolution is shed into a two dimensional chart. The plots are then analyzed and characterized in the perspective of fractal dimension. This information is integrated in two measures of the species’ complexity addressing its average and variability. The results are in close accordance with phylogenetics pointing quantitative aspects of the species’ genomic complexity.     

Wall and Siegmund Duality Relations for Birth and Death Chains with Reflecting Barrier

For a birth and death chain on the nonnegative integers with birth and death probabilities p _i and q _i 1 –p _i and reflecting barrier at 0, it is shown that the right tails of the probability of the first return from state 0 to state 0 are simple transition probabilities of a dual birth and death chain obtained by switching p _iand q _i. Combinatorial and analytical proofs are presented. Extensions and relations to other concepts of duality in the literature are discussed.     

On cuts and matchings in planar graphs

We study the max cut problem in graphs not contractible toK ₅, and optimum perfect matchings in planar graphs. We prove that both problems can be formulated as polynomial size linear programs.Supported by the joint project Combinatorial Optimization of the Natural Sciences and Engineering Research Council of Canada and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Emergent behaviors of a thermodynamic Cucker-Smale flock with a time-delay on a general digraph

We present emergent flocking dynamics of a thermodynamic Cucker-Smale (TCS) flock on a general digraph with spanning trees under the effect of communication time-delays. The TCS model describes a temporal evolution of mechanical and thermodynamic observables such as position, velocity and temperature of CS particles. In this paper, we study how variations in mechanical and thermodynamic variables can decay to zero along a time-independent network with position dependent weights from initial state configuration. For this, we provide a sufficient framework for a mechanical and thermodynamical flocking in terms of initial configuration, network topology, and system parameters. We also present several numerical examples and compare them with analytical results.     

The fifty percent rule revisited

Combinatorial reasoning is applied to the analysis of two kinds of dynamic storage allocation system to derive results about the degree and characteristics of memory fragmentation. The simple first-fit scheme with immediate replacement, discussed by Knuth, is analyzed further, providinginter alia a new derivation of the fifty percent rule. Next a system with garbage collections is considered, and the mean and variance of the number of holes following a garbage collection are determined, along with other results. The cell distributions resulting from these two idealized policies are contrasted.This research was supported in part by the National Science and Engineering Research Council of Canada under an operating grant.     

Temperature Correlation Function in the Absolutely Anisotropic XXZ Heisenberg Magnet

For the one-dimensional XXZ Heisenberg chain of spin 1/2 at = –, we calculate the two-time temperature correlation function of the third components of local spins. For the correlation function in the thermodynamic limit, we obtain the expression in terms of Fredholm determinants for linear integral operators.     

Onf-vectors and Betti numbers of multicomplexes

A multicomplexM is a collection of monomials closed under divisibility. For suchM we construct a cell complex M whosei-dimensional cells are in bijection with thef _i monomials ofM of degreei+1. The bijection is such that the inclusion relation of cells corresponds to divisibility of monomials. We then study relations between the numbersf _i and the Betti numbers of M. For squarefree monomials the construction specializes to the standard geometric realization of a simplicial complex.This work was supported by the Mittag-Leffler Institute during the Combinatorial Year program 1991–92. The second author also acknowledges support from the Serbian Science Foundation, Grant No. 0401D.     

On the Varieties of Parabolic Subgroups, their Generalizations and Combinatorial Applications

Investigations of homogeneous varieties T=(G:P) of all cosets of finite Coxeter or Chevalley groups G by their maximal parabolic subgroups P had been conducted at the Kalunin seminar at Kiev State University since the 1970s, as were investigations of their corresponding permutation groups, geometries and association schemes.In I. A. Faradev et al. (eds), Investigations in Algebraic Theory of Combinatorial Objects (Kluwer Acad. Publ., 1994), one can find some results on the investigation of noncomplete Galois correspondence between fusion schemes of the orbital scheme for (G,T) and overgroups of (G,T), as well as calculations of the intersectional indices of the Hecke algebra of (G,T). We will discuss additional results on this topic and consider questions related to the following problems: embeddings of varieties (G:P) into the Lie algebra corresponding to Chevalley group G; interpretations of Lie geometries, small Schubert cells, connections between the geometry of G and its associated Weyl geometry in terms of linear algebra, and applications of these problems to calculations performed in Lie geometries and association schemes; constructions of geometric objects arising from Kac–Moody Lie algebras and superalgebras, and applications of these constructions to investigations of graphs of large girth and large size.