共找到 20 条结果
Ordered logics and type systems have been used in a variety of applications including computational linguistics, memory allocation, stream processing, logical frameworks, parametricity, and enforcing security protocols. In most formulations, ordered types are also linear, requiring each resource to be used exactly once. Prior work by Kanovich et al. has investigated calculi that relax this constraint through subexponentials within a linear ordered logic. We generalize their work by using adjoint modalities to combine logics with varying fine-grained structural properties, including weakening, left contraction, right contraction, left mobility, and right mobility. We show that the resulting sequent calculus admits cut elimination. We further provide a natural deduction formulation in which structural rules are implicit, and show that proof checking for this system is decidable. This makes it a suitable foundation for an expressive adjoint programming language or logical framework.
Recently Yang-Roh-Jun introduced the notion of ordered BCI-algebras as a generalization of BCI-algebras. They also introduced the notions of homomorphisms and kernels of ordered BCI-algebras and investigated related properties. Here we extend their investigation to ordered homomorphisms, i.e., order-preserving homomorphisms. To this end, the notions of ordered homomorphism and kernel of ordered BCI-algebras are first defined. Next, properties associated with (ordered) subalgebras, (ordered) filters and direct products of ordered BCI-algebras are addressed.
Recently, the saturation problem of $0$-$1$ matrices gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this, we initiate the study of the saturation problem of ordered and cyclically ordered graphs. We prove that dichotomy holds also in these two cases, i.e., for a (cyclically) ordered graph its saturation function is either bounded or linear. We also determine the order of magnitude for large classes of (cyclically) ordered graphs, giving infinite many examples exhibiting both possible behaviours, answering a problem of Pálvölgyi. In particular, in the ordered case we define a natural subclass of ordered matchings, the class of linked matchings, and we start their systematic study, concentrating on linked matchings with at most three links and prove that many of them have bounded saturation function. In both the ordered and cyclically ordered case we also consider the semisaturation problem, where dichotomy holds as well and we can even fully characterize the graphs that have bounded semisaturation function.
An ordered graph is a graph equipped with a linear ordering of its vertex set. A pair of ordered graphs is Ramsey finite if it has only finitely many minimal ordered Ramsey graphs and Ramsey infinite otherwise. Here an ordered graph F is an ordered Ramsey graph of a pair (H,H') of ordered graphs if for any coloring of the edges of F in colors red and blue there is either a copy of H with all edges colored red or a copy of H' with all edges colored blue. Such an ordered Ramsey graph is minimal if neither of its proper subgraphs is an ordered Ramsey graph of (H,H'). If H=H' then H itself is called Ramsey finite. We show that a connected ordered graph is Ramsey finite if and only if it is a star with center being the first or the last vertex in the linear order. In general we prove that each Ramsey finite (not necessarily connected) ordered graph H has a pseudoforest as a Ramsey graph and therefore is a star forest with strong restrictions on the positions of the centers of the stars. In the asymmetric case we show that (H,H') is Ramsey finite whenever H is a so-called monotone matching. Among several further results we show that there are Ramsey finite pairs of ordered stars and orde
A mixed lattice is a partially ordered set with two mixed partial orderings that are linked by asymmetric upper and lower envelopes. These notions generalize the join and meet operations of a lattice. In the present paper, we study different types of partially ordered semigroups with two mixed orderings, and investigate their relationship to subsemigroups of mixed lattice groups, which are partially ordered groups with a similar order structure. We also consider Archimedean orderings, and we show that elements of finite order cannot exist in a rather general class of Archimedean mixed lattice groups. Moreover, we give an example of a non-Archimedean mixed lattice group that contains an element of finite order.
We introduce the theory of normal ordered grammars, which gives a natural generalization of the normal ordering problem. To illustrate the main idea, we explore normal ordered grammars associated with the Eulerian polynomials and the second-order Eulerian polynomials. In particular, we present a normal ordered grammatical interpretation for the (cdes,cyc) (p,q)-Eulerian polynomials, where cdes and cyc are the cycle descent and cycle statistics, respectively. The exponential generating function for a family of polynomials, generated by a normal ordered grammar associated with the second-order Eulerian polynomials, reveals an interesting feature: its expression involves the generating function for Catalan numbers as its exponent. In the final part, we discuss some normal ordered grammars related to the type B Eulerian polynomials. A normal ordered grammatical interpretation of the up-down run polynomial is also established.
The emerging theory of graph limits exhibits an analytic perspective on graphs, showing that many important concepts and tools in graph theory and its applications can be described more naturally (and sometimes proved more easily) in analytic language. We extend the theory of graph limits to the ordered setting, presenting a limit object for dense vertex-ordered graphs, which we call an orderon. As a special case, this yields limit objects for matrices whose rows and columns are ordered, and for dynamic graphs that expand (via vertex insertions) over time. Along the way, we devise an ordered locality-preserving variant of the cut distance between ordered graphs, showing that two graphs are close with respect to this distance if and only if they are similar in terms of their ordered subgraph frequencies. We show that the space of orderons is compact with respect to this distance notion, which is key to a successful analysis of combinatorial objects through their limits. We derive several applications of the ordered limit theory in extremal combinatorics, sampling, and property testing in ordered graphs. In particular, we prove a new ordered analogue of the well-known result by Alon
In this paper, we describe a way of turning a seminormed preordered vector space into an Archimedean order unit space. We show that this construction satisfies a universal property similar to that of the Archimedeanization of Paulsen and Tomforde, and we give a number of applications of our result in ordered vector spaces and in matrix ordered operator spaces. In ordered vector spaces, we use our our Archimedean order unitzation to shed new light on normality criteria for seminorms. In matrix ordered operator spaces, we prove several new results about Werner's "partial unitization": we give a simplified "internal" description of the positive cone of Werner's partial unitization, and we prove a necessary and sufficient condition for the embedding of a matrix ordered operator space in its partial unitization to be a complete isomorphism. This last result was already announced in Werner's 2002 paper, but to our knowledge no proof exists in the literature.
It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering on their vertex set, and the function f(H) = sup{chi(G) | G in Forb(H)} where Forb(H) denotes the set of all ordered graphs that do not contain a copy of H. If H contains a cycle, then as in the case of unordered graphs, f(H) is infinity. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with infinite f(H). An ordered graph is crossing if there are two edges uv and u'v' with u < u' < v < v'. For connected crossing ordered graphs H we reduce the problem of determining whether f(H) is finite to a family of so-called monotonically alternating trees. For non-crossing H we prove that f(H) is finite if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f(H) <= 2^|V(H)| and that f(H) <= 2|V(H)|-3 if H is connected.
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems $\mathsf{Hamiltonian\ Path}$ and $\mathsf{Hamiltonian\ Cycle}$ are in $\mathsf{FPT}$. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are $\mathsf{W[1]}$-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in $\mathsf{XP}$ time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some $\mathsf{FPT}$ algorithms, e.g., for edge distance to block. Additionally, we prove para-$\mathsf{NP}$-hardness when considered with the edge clique cover number.
The Maximal Covering Location Problem (MCLP) is a classical location problem where a company maximizes the demand covered by placing a given number of facilities, and each demand node is covered if the closest facility is within a predetermined radius. In the cooperative version of the problem (CMCLP), it is assumed that the facilities of the decision maker act cooperatively to increase the customersz' attraction towards the company. In this sense, a demand node is covered if the aggregated partial attractions (or partial coverings) of open facilities exceed a threshold. In this work, we generalize the CMCLP introducing an Ordered Median function (OMf), a function that assigns importance weights to the sorted partial attractions of each customer and then aggregates the weighted attractions to provide the total level of attraction. We name this problem the Ordered Cooperative Maximum Covering Location Problem (OCMCLP). The OMf serves as a means to compute the total attraction of each customer to the company as an aggregation of ordered partial attractions and constitutes a unifying framework for CMCLP models. We introduce a multiperiod stochastic non-linear formulation for the CMCLP
Ordered random vectors are frequently encountered in many problems. The generalized order statistics (GOS) and sequential order statistics (SOS) are two general models for ordered random vectors. However, these two models do not capture the dependency structures that are present in the underlying random variables. In this paper, we study the developed sequential order statistics (DSOS) and developed generalized order statistics (DGOS) models that describe the dependency structures of ordered random vectors. We then study various univariate and multivariate ordering properties of DSOS and DGOS models under Archimedean copula. We consider both one-sample and two-sample scenarios and develop corresponding results.
We investigate canonical factorizations of ordered functors of ordered groupoids through star-surjective functors. Our main construction is a quotient ordered groupoid, depending on an ordered version of the notion of normal subgroupoid, that results is the factorization of an ordered functor as a star-surjective functor followed by a star-injective functor. Any star-injective functor possesses a universal factorization through a covering, by Ehresmann's Maximum Enlargement Theorem. We also show that any ordered functor has a canonical factorization through a functor with the ordered homotopy lifting property.
An element e of an ordered semigroup $(S,\cdot,\leq)$ is called an ordered idempotent if $e\leq e^2$. We call an ordered semigroup $S$ idempotent ordered semigroup if every element of $S$ is an ordered idempotent. Every idempotent semigroup is a complete semilattice of rectangular idempotent semigroups and in this way we arrive to many other important classes of idempotent ordered semigroups.
The purpose of this paper is to study the generalization of inverse semigroups (without order). An ordered semigroup S is called an inverse ordered semigroup if for every a 2 S, any two inverses of a are H-related. We prove that an ordered semigroup is complete semilattice of t-simple ordered semigroups if and only if it is completely regular and inverse. Furthermore characterizations of inverse ordered semigroups have been characterized by their ordered idempotents.
Decomposable ordered structures were introduced in \cite{OnSt} to develop a general framework to study `finite-dimensional' totally ordered structures. This paper continues this work to include decomposable structures on which a ordered group operation is defined on the structure. The main result at this level of generality asserts that any such group is supersolvable, and that topologically it is homeomorphic to the product of o-minimal groups. Then, working in an o-minimal ordered field $\mathcal R$ satisfying some additional assumptions, in Sections 3-7 definable ordered groups of dimension 2 and 3 are completely analyzed modulo definable group isomorphism. Lastly, this analysis is refined to provide a full description of these groups with respect to definable ordered group isomorphism.
In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median hub location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
By a result known as Rieger's theorem (1956), there is a one-to-one correspondence, assigning to each cyclically ordered group $H$ a pair $(G,z)$ where $G$ is a totally ordered group and $z$ is an element in the center of $G$, generating a cofinal subgroup $\langle z\rangle$ of $G$, and such that the quotient group $G/\langle z\rangle$ is isomorphic to $H$. We first establish that, in this correspondence, the first order theory of the cyclically ordered group $H$ is uniquely determined by the first order theory of the pair $(G,z)$. Then we prove that the class of cyclically ordered groups is an elementary class and give an axiom system for it. Finally we show that, in opposition to the fact that all theories of totally Abelian ordered groups have the same universal part, there are uncountably many universal theories of Abelian cyclically ordered groups. We give for each of these universal theories an invariant, which is a pair of subgroups of the group of unimodular complex numbers.
In $α$-RuCl$_3$, an external magnetic field applied within the honeycomb plane can induce a transition from a magnetically ordered state to a disordered state that is potentially related to the Kitaev quantum spin liquid. In zero field, single crystals with minimal stacking faults display a low-temperature state with in-plane zigzag antiferromagnetic order and a three-layer periodicity in the direction perpendicular to the honeycomb planes. Here, we present angle-dependent magnetization, ac susceptibility, and thermal transport data that demonstrate the presence of an additional intermediate-field ordered state at fields below the transition to the disordered phase. Neutron diffraction results show that the magnetic structure in this phase is characterized by a six-layer periodicity in the direction perpendicular to the honeycomb planes. Theoretically, the intermediate ordered phase can be accounted for by including spin-anisotropic couplings between the layers in a three-dimensional spin model. Together, this demonstrates the importance of interlayer exchange interactions in $α$-RuCl$_3$.
We show that a lattice-ordered field (not necessarily commutative) is totally ordered if and only if each square is positive, answering a generalized question of Conrad and Dauns (Pacific J. Math. 30 (1969), 385--398) in the affirmative. As a consequence, any lattice-ordered skew field in (Brumfiel, Partially ordered rings and semi-algebraic geometry. Cambridge University Press, 1979) is totally ordered. Furthermore, we note that every lattice order determined by a {\it pre-positive cone} $P$ on a skew-filed $F$ is linearly ordered since $F^2\subseteq P$ (see P restel, Lectures on formally real fields, Lecture Notes in mathematics, 1093, Springer-Verlag, 1984).