Search results for "Preorder"
showing 7 items of 7 documents
The diamond partial order for strong Rickart rings
2016
The diamond partial order has been first introduced for matrices, and then discussed also in the general context of *-regular rings. We extend this notion to Rickart rings, and state various properties of the diamond order living on the so-called strong Rickart rings. In particular, it is compared with the weak space preorder and the star order; also existence of certain meets and joins under diamond order is discussed.
Lp-Spaces
1998
For (X, ℜ, μ) a positive measure space, it has already been noted that μ - a.e. equality is an equivalence relation, and the relation ≤ μ-a.e. a preorder, on.This section studies the structure of the equivalence classes into which μ-a,e. equality partitions.Since the set X/X( ℜ) is always u-null (2.7.7 a)), only the function values on the set X(ℜ) have any significance when equivalence classes are formed: whether we form equivalence classes by partitioning or by partitioningX(ℜ) the resulting structures will be isomorphic. Nevertheless, it is natural to allow functions on an arbitrary X ⊃ X(ℜ). Our choice is to form μ-equivalence classes by partitioning the set X(ℜ). For arbitrary X ⊃ X(ℜ),…
Simulation is decidable for one-counter nets
1998
We prove that the simulation preorder is decidable for the class of one-counter nets. A one-counter net consists of a finite-state machine operating on a variable (counter) which ranges over the natural numbers. Each transition can increase or decrease the value of the counter. A transition may not be performed if this implies that the value of the counter becomes negative. The class of one-counter nets is computationally equivalent to the class of Petri nets with one unbounded place, and to the class of pushdown automata where the stack alphabet is restricted to one symbol. To our knowledge, this is the first result in the literature which gives a positive answer to the decidability of sim…
General decidability theorems for infinite-state systems
2002
Over the last few years there has been an increasing research effort directed towards the automatic verification of infinite state systems. This paper is concerned with identifying general mathematical structures which can serve as sufficient conditions for achieving decidability. We present decidability results for a class of systems (called well-structured systems), which consist of a finite control part operating on an infinite data domain. The results assume that the data domain is equipped with a well-ordered and well-founded preorder such that the transition relation is "monotonic" (is a simulation) with respect to the preorder. We show that the following properties are decidable for …
Some dissenting views on the transitivity of individual preference
1990
(1) The transitivity property is not a necessary condition for the rationality of all individual preference relations. (2) A weakened definition of the transitivity is not necessarily relevant. (3) The non-transitivity of fuzzy preference relations is not inconsistent with a fuzzy total preorder structure on the set of alternatives.
On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations
2009
We show that every finitely satisfiable two-variable first-order formula with two equivalence relations has a model of size at most triply exponential with respect to its length. Thus the finite satisfiability problem for two-variable logic over the class of structures with two equivalence relations is decidable in nondeterministic triply exponential time. We also show that replacing one of the equivalence relations in the considered class of structures by a relation which is only required to be transitive leads to undecidability. This sharpens the earlier result that two-variable logic is undecidable over the class of structures with two transitive relations.
Algorithmic Analysis of Programs with Well Quasi-ordered Domains
2000
AbstractOver the past few years increasing research effort has been directed towards the automatic verification of infinite-state systems. This paper is concerned with identifying general mathematical structures which can serve as sufficient conditions for achieving decidability. We present decidability results for a class of systems (called well-structured systems) which consist of a finite control part operating on an infinite data domain. The results assume that the data domain is equipped with a preorder which is a well quasi-ordering, such that the transition relation is “monotonic” (a simulation) with respect to the preorder. We show that the following properties are decidable for wel…