Recursive linear orders with recursive successivities

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities $\text{U}$ is recursively categorical if every recursive linear order with recursive successivities isomorphic to $\text{U}$ is in fact recursively isomorphic to $\text{U}$. We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k₁+g₁+k₂+g₂+…+g_n-1+k_n where each k_n is a finite order type, non-empty for i?{2,…,n-1} and each g_i is an order type from among {ω,ω^*,ω+ω^*}∪{k·η:k<ω}.     

Recursive blocked algorithms for linear systems with Kronecker product structure

Numerical Algorithms - Recursive blocked algorithms have proven to be highly efficient at the numerical solution of the Sylvester matrix equation and its generalizations. In this work, we show that...     

A comparison of algorithms for minimizing bumps in linear extensions of partial orders

The notion of bumps deals with a property of linear extensions of a partial order. Let P define a partial order on a set X and let L define a linear extension of P. A bump occurs whenever elements x and y in X are adjacent in both P and L. Heuristics have been developed to construct linear extensions of a partial order that should tend to minimize bumps. This paper presents results of a computer simulation study that compares the performance of bump minimizing algorithms.     

Matching structure and the matching lattice

The matching polyhedron, i.e., the convex hull of (incidence vectors of) perfect matchings of a graph was characterized by Edmonds; this result is the key to a large part of polyhedral combinatorics and is used in many combinatorial algorithms. The linear hull of perfect matchings was characterized by Naddef, and by Edmonds, Lovász, and Pulleyblank. In this paper we describe the lattice generated by these vectors, i.e., the set of all integer linear combinations of perfect matchings. It turns out that the Petersen graph is, in a sense, the only difficult example. Our results also imply a characterization of the linear hull of perfect matchings over fields of characteristic different from 0. The main method is a decomposition theory developed by Kotzig, Lovász, and Plummer, which breaks down every graph into a number of graphs called bricks with very good matching properties. The number of Petersen graphs among these bricks will turn out to be an essential parameter of the matching lattice. Some refinements of the decomposition theory are also given. Among others, we show that the list of bricks obtained during the decomposition procedure is independent of the special choices made during the procedure.     

Automata on ordinals and automaticity of linear orders

We investigate structures recognizable by finite state automata with an input tape of length a limit ordinal. At limits, the set of states which appear unboundedly often before the limit are mapped to a limit state. We describe a method for proving non-automaticity and apply this to determine the optimal bounds for the ranks of linear orders recognized by such automata.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

The number of linear orders on a field

An example is given of a field which can be ordered in exactly ways where is a given cardinal number.Translated from Matematicheskie Zametki, Vol. 6, No. 2, pp. 201–211, August, 1969.     

Construction of lattice orders on the semigroup ring of a positive rooted monoid

Lattice orders on the semigroup ring of a positive rooted monoid are constructed, and it is shown how to make the monoid ring into a lattice-ordered ring with squares positive in various ways. It is proved that under certain conditions these are all of the lattice orders that make the monoid ring into a lattice-ordered ring. In particular, all of the partial orders on the polynomial ring A[x] in one positive variable are determined for which the ring is not totally ordered but is a lattice-ordered ring with the property that the square of every element is positive. In the last section some basic properties of d-elements are considered, and they are used to characterize lattice-ordered division rings that are quadratic extensions of totally ordered division rings.     

Complexity of computing median linear orders and variants

Given a finite set X and a collection Π of linear orders defined on X, computing a median linear order (Condorcet-Kemenyʼs problem) consists in determining a linear order minimizing the remoteness from Π. This remoteness is based on the symmetric distance, and measures the number of disagreements between O and Π. In the context of voting theory, X can be considered as a set of candidates and the linear orders of Π as the preferences of voters, while a linear order minimizing the remoteness from Π can be adopted as the collective ranking of the candidates with respect to the votersʼ opinions. This paper studies the complexity of this problem and of several variants of it: computing a median order, computing a winner according to this method, checking that a given candidate is a winner and so on. We try to locate these problems inside the polynomial hierarchy.     

Trees, linear orders and Gateaux smooth norms

We introduce a linearly ordered set Z and use it to prove anecessity condition for the existence of a Gâteaux smoothnorm on ₀(), where is a tree. This criterion is directly analogousto the corresponding equivalent condition for Fréchetsmooth norms. In addition, we prove that if ₀() admits a Gâteauxsmooth lattice norm then it also admits a lattice norm withstrictly convex dual norm.     

The Boolean algebra of the theory of linear orders

We characterize the isomorphism type of the Boolean algebra of sentences of the theory of linear orders. It is isomorphic to the sentence algebras of the theory of equivalence relations, the theory of permutations and the theory of well-orderings. This work was partially supported by the National Science Foundation under research grant MCS 76-07249.     

Data structures and algorithms for approximate string matching

This paper surveys techniques for designing efficient sequential and parallel approximate string matching algorithms. Special attention is given to the methods for the construction of data structures that efficiently support primitive operations needed in approximate string matching.     

Numerical linear algorithms and group theory

Most methods for solving linear systems Ax=b are founded on the ability to split up the matrix A in the form of a product A=G·R with G belonging to a subgroup of the general linear group Gl(n,R) and R being a regular upper triangular matrix. In the same way, the calculation of the eigenvalues of a matrix by the use of an algorithm of the Rutishauser type is based on a G·R decomposition for the matrix. Our aim in this article will be to show the importance of the notion of splitting up, to set out the conditions under which it may be used and to show how it enables us to generate new algorithms.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Normalizable linear orders and generic computations in finite models

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than with defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. Received: 13 July 1996     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.