Search

In general, representations of interval orders may use an arbitrary set of interval lengths. We can define subclasses of interval orders by restricting the allowable lengths of intervals. Motivated by a recent paper of Keller, Trenk, and Young, we study the dimension of posets in some of these subclasses. Among other results, we answer several of their questions, and we simplify the proof of one of their main results. [ABSTRACT FROM AUTHOR]

This paper examines the logic of conditional obligation, which originates from the works of Hansson, Lewis, and others. Some weakened forms of transitivity of the betterness relation are studied. These are quasi-transitivity, Suzumura consistency, acyclicity and the interval order condition. The first three do not change the logic. The axiomatic system is the same whether or not they are introduced. This holds true under a rule of interpretation in terms of maximality and strong maximality. The interval order condition gives rise to a new axiom. Depending on the rule of interpretation, this one changes. With the rule of maximality, one obtains the principle known as disjunctive rationality. With the rule of strong maximality, one obtains the Spohn axiom (also known as the principle of rational monotony, or Lewis' axiom CV). A completeness theorem further substantiates these observations. For interval order, this yields the finite model property and decidability of the calculus. [ABSTRACT FROM AUTHOR]

One way to verify the concurrent system is to sort the read and write events and control events in the concurrent system according to the sequence relationship, either in a partial order, or in a strict order. Due to the concurrency of the events and the timing of the written data events, there is an overlap between the events, which requires an interval order for analysis. The order structure of the entire interval order is represented by the start and end sequences, and the order is observed for all equivalent interval orders. Mazurkiewicz traces, Comtraces are hierarchical traces, but neither can describe the interval trace. The petri interval trace with data is the technique to solve the problem in this paper, DPN, the Petri net with data, to describe the interval trace of read and write data. The method used is a BE (Beginnings and Endings) sequence to represent a class of runs based on the interval sequence. The case multi-threaded system represents the interval of writing events, and according to the unfolding of Petri net, the analysis of the running trace involved by read and write data events is successfully analyzed. [ABSTRACT FROM AUTHOR]

We provide upper bounds on the L(p, q)-labeling number of graphs which have interval (or circular-arc) representations via simple greedy algorithms. We prove that there exists an L(p, q)-labeling with a span at most max{2(p+ q-1)Δ-4q+2, (2p-1)μ+(2q-1)Δ-2q+1} for interval k-graphs, max{p, q}Δ for interval graphs, 3max{p, q}Δ+p for circular-arc graphs, 2(p+q-1)Δ-2q +1 for permutation graphs and (2p-1)Δ+(2q -1)(μ-1) for cointerval graphs. In particular, these improve existing bounds on L(p, q)-labeling of interval graphs and L(2, 1)-labeling of permutation graphs. Furthermore, we provide upper bounds on the coloring of the squares of aforementioned classes. [ABSTRACT FROM AUTHOR]

We propose a novel mapping from a space of interval-valued functions defined on an arbitrary set to the family of closed subintervals of nonnegative extended real numbers, called the interval-valued Choquet-Sugeno-like operator. It is based on the notion of the Choquet-Sugeno-like operator and the interval-valued seminormed fuzzy operator introduced by Boczek et al. (2021) and generalizes many interval-valued operators known in the literature, such as n -ary interval-valued aggregation operators, interval-valued ordered weighting average operators, interval-valued seminormed fuzzy operators, and discrete interval-valued Choquet integral. We study its properties and show that it can be used to aggregate interval-valued data. [ABSTRACT FROM AUTHOR]

Rabinovitch showed in 1978 that the interval orders having a representation consisting of only closed unit intervals have order dimension at most 3 . This article shows that the same dimension bound applies to two other classes of posets: those having a representation consisting of unit intervals (but with a mixture of open and closed intervals allowed) and those having a representation consisting of closed intervals with lengths in 0 , 1 . [ABSTRACT FROM AUTHOR]

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower's problem. More precisely, adopting the robust optimization approach and assuming that the follower's profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower's reaction from the leader's perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader's objective function. [ABSTRACT FROM AUTHOR]

Abstract Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset.

The inequality between genders is a problem virtually in all countries. A comparison among 28 nations of the European Union together with a data set corresponding to a population weighted average of all European Union nations is performed for the years 2006, 2010 and 2017, respectively. In order to compare the nations mutually, six indicators out of the United Nation's Sustainable Development Goal No 5 are scrutinized. Methods of Discrete Mathematics are applied as a tool to perform the comparisons methods. Partial order is an appropriate tool to inspect the role of all these six indicators to compare the nations. It is shown that an aggregation method is possible without the difficult task to introduce specific weights to the single indicators. Beyond this it is assumed that the data are associated with some uncertainty that should be taken into account. As a methodological result, we show that a special partial order is recommendable, the interval order; furthermore, a crude classification is found with Denmark at the top, Germany in the middle field and Czech Republic in a position which requires obviously some improvements. Further, applying an identical analytical methodology the development in gender equality over the period 2006 to 2017 for Denmark, Germany, and the Czech Republic was studied applying the population averaged data for the European Union as a reference point. [ABSTRACT FROM AUTHOR]

Given a partial order Q , its semiorder dimension is the smallest number of semiorders whose intersection is Q. When we look at the class of partial orders of fixed semiorder dimension k , no characterization is known, even in the case k = 2. In this paper, we give a characterization of the class of interval orders with semiorder dimension two. It follows from our results that partial orders that are interval orders with semiorder dimension two can be recognized efficiently. As our characterization makes use of a certain substructure, we also discuss the possibility of a forbidden suborder characterization. We give a partial answer to this question by listing all forbidden suborders for a special case. We further transfer our characterization result to the class of interval graphs that induce orders with semiorder dimension two. [ABSTRACT FROM AUTHOR]

Let λ ∈ 0 , 1 2 . We prove that, for ordered sets P of order dimension 2 and for interval orders, the ratio of the number of automorphisms to the number of endomorphisms is asymptotically bounded by 2 − | P | λ . The key to the proof is to establish this bound for certain types of lexicographic sums. [ABSTRACT FROM AUTHOR]

Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset. [ABSTRACT FROM AUTHOR]

In this paper, we provide a characterization of the existence of a representation of an interval order on a topological space in the general case by means of a pair of continuous functions, when neither the functions nor the topological space are required to satisfy any particular assumptions. Such a characterization is based on a suitable continuity assumption of the binary relation, called weak continuity. In this way, we generalize all the previous results on the continuous representability of interval orders, and also of total preorders, as particular cases. [ABSTRACT FROM AUTHOR]

It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P = NP. In this paper, we show that this result holds even when the premises in the implicational base are of size at most two. Then we show using hypergraph dualization that the problem can be solved in output quasi-polynomial time whenever the implicational base has bounded independent-width, defined as the size of a maximum set of implications having independent conclusions. Lattices that share this property include distributive lattices coded by the ideals of an interval order, when both the independent-width and the size of the premises equal one. [ABSTRACT FROM AUTHOR]

Multiple definitions have been put forward in the literature to measure the differences between two interval-valued fuzzy sets. However, in most cases, the outcome is just a real value, although an interval could be more appropriate in this environment. This is the starting point of this contribution. Thus, we revisit the axioms that a measure of the difference between two interval-valued fuzzy sets should satisfy, paying special attention to the condition of monotonicity in the sense that the closer the intervals are, the smaller the measure of difference between them is. Its formalisation leads to very different concepts: distances, divergences and dissimilarities. We have proven that distances and divergences lead to contradictory properties for this kind of sets. Therefore, we conclude that dissimilarities are the only appropriate measures to measure the difference between two interval-valued fuzzy sets when the outcome is an interval.

The combined work of Bousquet-Mélou, Claesson, Dukes, Jelínek, Kitaev, Kubitzke and Parviainen has resulted in non-trivial bijections among ascent sequences, (2+2)-free posets, upper-triangular integer matrices, and pattern-avoiding permutations. To probe the finer behaviour of these bijections, we study two types of restrictions on ascent sequences. These restrictions are motivated by our results that their images under the bijections are natural and combinatorially significant. In addition, for one restriction, we are able to determine the effect of poset duality on the corresponding ascent sequences, matrices and permutations, thereby answering a question of the first author and Parviainen in this case. The second restriction should appeal to Catalaniacs. [ABSTRACT FROM AUTHOR]

A poset P = (X , ≺) has an interval representation if each x ∈ X can be assigned a real interval I x so that x ≺ y in P if and only if I x lies completely to the left of I y. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X , ≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x ∈ X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation. [ABSTRACT FROM AUTHOR]

A representation of interval orders by sequences of antichains is discussed, and its relationship to the Fishburn's representation by sequences of the beginnings and endings of domain elements is analysed in detail. Moreover, an operational semantics based on sequences of maximal antichains is proposed and investigated for a general class of safe Petri nets with context arcs. [ABSTRACT FROM AUTHOR]

We show that the protocol complex formalization of fault-tolerant protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the protocol complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: protocol complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures. [ABSTRACT FROM AUTHOR]

The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D(x) ∩ N+D(y) ≠ ∅ or N−D(x) ∩ N−D(y) ≠ ∅, where N+D(x) (resp. N−D(x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function f : V → R on the set V and a positive real number δ ∈ R such that (x, y) ∈ A if and only if f(x) > f(y)+δ. A digraph D = (V,A) is called an interval order if there exists an assignment J of a closed real interval J(x) ⊂ R to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) > max J(y). Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders