Search

Let 휅 be an inaccessible cardinal, 픘 a universal algebra, and ∼ the equivalence relation on U κ of eventual equality. From mild assumptions on 휅, we give general constructions of E ∈ End (U κ / ∼) satisfying E ∘ E = E which do not descend from Δ ∈ End ⁡ (U κ) having small strong supports. As an application, there exists an E ∈ End (Z κ / ∼) which does not come from a Δ ∈ End ⁡ (Z κ) . [ABSTRACT FROM AUTHOR]

In this paper, a class of generalized convex games is introduced. Existence properties of Nash equilibria, in mixed and pure strategies, are proposed. These properties are studied by considering limit cases related to a specific class of semi-lattice games. We propose an interpretation of our results based on Atkinson's notion of generalized means. We also show that our approach makes it possible to propose a preference scheme taking into account the notion of prioritarianism. [ABSTRACT FROM AUTHOR]

This paper is a reaction to Watumull and Roberts (2023, https://doi.org/10.5964/bioling.12393). [ABSTRACT FROM AUTHOR]

An exclusive disjunction is true when exactly one of the disjuncts is true. In the case of the familiar binary exclusive disjunction, we have a formula occurring as the first disjunct and a formula occurring as the second disjunct, so, if what we have is two formula-tokens of the same formula-type—one formula occurring twice over, that is—the question arises as to whether, when that formula is true, to count the case as one in which exactly one of the disjuncts is true, counting by type, or as a case in which two disjuncts are true, counting by token. The latter is the standard answer: counting by tokens. James McCawley once suggested that, when the exclusively disjunctive construction in natural language (well, in English at least) is at issue, the construction should be treated as involving a multigrade connective whose semantic treatment is sensitive to the set of disjuncts rather than the corresponding multiset. Without any commitment as to whether there actually is such a construction (in English), and conceding that for obvious pragmatic reasons such 'repeated disjunct' cases would be at best highly marginal, we note that for the binary case, this requires a nonstandard answer—count by type rather than by token—to the earlier question, and thus, an idempotent exclusive disjunction connective. Section 2 explores that idea and Section 3, a further idempotent variant for which it is the propositions expressed by the disjuncts, rather than the disjuncts themselves, that get counted once only in the case of repetitions. Sections 1 and 4 respectively set the stage for these investigations and conclude the discussion (after noting an intimate connection between the logic of Section 3 and the modal logic S5). More detailed considerations of points arising from the discussion but otherwise in danger of interrupting the flow are deferred to a 'Longer Notes' appendix at the end (Section 5.) [ABSTRACT FROM AUTHOR]

Interval numbers multiple attribute decision‐making (MADM) is an important branch of uncertainty decision theory, and the decision result largely depends on the selection of the aggregation operator. In this paper, we analyze the ordered weighted average (OWA) operator, which is an averaging aggregation operator. The OWA operator provides an aggregation method between the minimum and maximum operators. Moreover, we further analyze some of extensions about OWA operator, and pay special attention to the Bonferroni means and OWA (BON‐OWA) operator. Note that the BON‐OWA operator only aggregate the input arguments which are exact numbers. Under normal circumstances, decision makers is difficult to provide a clear evaluation value for attribute and most of them are described by vague information. When the decision information is an interval numbers, the BON‐OWA operator cannot describe decision result accurately. Under these environments, we proposed the interval numbers BON‐OWA (IBr,q‐OWA) operator to deal with the vague decision information in this paper. Then we consider their main properties, such as idempotence, monotonicity, and boundedness and prove them. Besides, a wide range of special aggregation operators are found in changing parameter values, such as the square mean and max operator, and so on. We also compare the ranking method of the interval numbers based on Boolean matrix. As a result, the combination of IBr,q‐OWA operator makes the decision result more scientific. Finally, a new approach for decision‐making problem is developed based on the IBr,q‐OWA operator, which shows the effectiveness in practical examples. [ABSTRACT FROM AUTHOR]

Mission-critical embedded systems simultaneously run multiple graphics-processing-unit (GPU) computing tasks with different criticality and timeliness requirements. Considerable research effort has been dedicated to supporting the preemptive priority scheduling of GPU kernels. However, hardware-supported preemption leads to lengthy scheduling delays and complicated designs, and most software approaches depend on the voluntary yielding of GPU resources from restructured kernels. We propose a preemptive GPU kernel scheduling scheme that harnesses the idempotence property of kernels. The proposed scheme distinguishes idempotent kernels through static source code analysis. If a kernel is not idempotent, then GPU kernels are transactionized at the operating system (OS) level. Both idempotent and transactionized kernels can be aborted at any point during their execution and rolled back to their initial state for reexecution. Therefore, low-priority kernel instances can be preempted for high-priority kernel instances and reexecuted after the GPU becomes available again. Our evaluation using the Rodinia benchmark suite showed that the proposed approach limits the preemption delay to 18 $\mu$ μ s in the 99.9th percentile, with an average delay in execution time of less than 10 percent for high-priority tasks under a heavy load in most cases. [ABSTRACT FROM AUTHOR]

In this article, we address two problems related to idempotent anti-unification. First, we show that there exists an anti-unification problem with a single idempotent symbol that has an infinite minimal complete set of generalizations. It means that anti-unification with a single idempotent symbol has infinitary or nullary generalization type, similar to anti-unification with two idempotent symbols, shown earlier by Loïc Pottier. Next, we develop an algorithm that takes an arbitrary idempotent anti-unification problem and computes a representation of its solution set in the form of a regular tree grammar. The algorithm does not depend on the number of idempotent function symbols in the input terms. The language generated by the grammar is the minimal complete set of generalizations of the given anti-unification problem, which implies that idempotent anti-unification is infinitary. [ABSTRACT FROM AUTHOR]

Aggregation functions are mathematical operators that merge given data in order to obtain a global value that preserves the information given by the data as much as possible. In most practical applications, this value is expected to be between the infimum and the supremum of the given data, which is guaranteed only when the aggregation functions are idempotent. Ordered weighted averaging (OWA) operators are particular cases of this kind of function, with the particularity that the obtained global value depends on neither the source nor the expert that provides each datum, but only on the set of values. They have been classified by means of the orness--a measurement of the proximity of an OWA operator to the OR-operator. In this paper, the concept of orness is extended to the framework of idempotent aggregation functions defined both on the real unit interval and on a complete lattice with a local finiteness condition. [ABSTRACT FROM AUTHOR]

In this paper, we characterize idempotent Toeplitz sign patterns and idempotent Hankel sign patterns. Our work extends some existing results. [ABSTRACT FROM AUTHOR]

We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℝ, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting m denote the space requirements, we prove a lower bound for general semigroups of $\widetilde{\varOmega}(n^{1-1/(d+1)}/m^{1/(d+1)})$ and for integral semigroups of $\widetilde{\varOmega}(n/m^{1/d})$. Our lower bounds are proved in the semigroup arithmetic model. Neglecting logarithmic factors, our result for integral semigroups matches the best known upper bound due to Matoušek. Our result for general semigroups improves upon the best known lower bound due to Brönnimann, Chazelle, and Pach. Moreover, Fonseca and Mount have shown that, given uniformly distributed points, halfspace range queries over idempotent semigroups can be answered in O( n/ m) time in the semigroup arithmetic model. As our lower bounds are established for uniformly distributed point sets, it follows that they also resolve the computational complexity of halfspace range searching over idempotent semigroups in this important special case. [ABSTRACT FROM AUTHOR]

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation. [ABSTRACT FROM AUTHOR]

Our first paper introduced block splitting operators on the complete lattice of partial partitions, studied their algebraic properties and characterized block splitting openings (kernel operators) in terms of partial connections. In this second paper we study non-isotone idempotent block splitting operators on partial partitions. In particular we analyse the following two constructions: These operators belong to two families of idempotent operators generalizing openings that the author studied previously. In the same way as the openings analysed in the first paper, these two types of idempotent operators underlie recent image segmentation approaches due to Serra and Soille. [ABSTRACT FROM AUTHOR]

A video coding system is desirable to be idempotent or re-loss-free (RLF) in multigeneration coding. This paper shows that H.264 coding may suffer severe re-loss during recompression in common encoding modes. The multigeneration coding flow of a general hybrid coding is analyzed and a sufficient condition is presented for an RLF hybrid coding system. There are four key mechanisms to achieve RLF coding: RLF transform and quantization, Preserving Q Clipping, Preserving Q Deblocking, and Prediction Mode and Q Identification. Finally, the paper describes some future work on RLF coding. [ABSTRACT FROM AUTHOR]

Given an n-element point set in ℝ d, the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam( η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup ( S,+) is idempotent if x+ x= x for all x∈ S, and it is integral if for all k≥2, the k-fold sum x+ ⋅⋅⋅+ x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least $\varOmega(1/{\varepsilon }^{d-2\sqrt{d}})$ . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ ε)( d−1)/2log (1/ ε)) time using O( n/ ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ ε)( d−1)/2). This bound is in the decision-tree model and holds irrespective of space. [ABSTRACT FROM AUTHOR]

Let Mn(F) be the space of all n × n matrices over a field F of characteristic not 2, and let Pn(F) be the subset of Mn(F) consisting of all n × n idempotent matrices. We denote by Φn(F) the set of all maps from Mn(F) to itself satisfying A-λB∈Pn(F) implies [image omitted] for every A,B∈Mn(F) and λ∈F. In this note, we prove that φ∈Φn(F) if and only if there exist δ∈{0,1} and an invertible matrix P∈Mn(F) such that either [image omitted] for every A∈Mn(F), or φ(A)=δPATP-1 for every A∈Mn(F). This improves the result of some related references. [ABSTRACT FROM AUTHOR]

Suppose F is an arbitrary field. Let |F| be the number of the elements of F. Let T n (F) be the space of all nxn upper-triangular matrices over F. A map Ψ: T N (F) → T N (F) is said to preserve idempotence if A - λ B is idempotent if and only if Ψ (A) - λΨ(B) is idempotent for any A, B ∈ T n (F) and λ ∈ F. It is shown that: when the characteristic of F is not 2, |F| >3 and n ≥ 3, Ψ: T n (F) → T n (F) is a map preserving idempotence if and only if there exists an invertible matrix P τ T n (F) such that either ϕ (A) = PAP −1 for every A ∈ T n (F) or Ψ (A) = PJA t JP −1 for every A ∈ T n (F), where J = ∑ n=1 n E i,n+1− i and Eij is the matrix with 1 in the (i,j)th entry and 0 elsewhere. [ABSTRACT FROM AUTHOR]

One aspect of the utility of gambling may evidence itself in failures of idempotence, i.e., when all chance outcomes give rise to the same consequence the `gamble' may not be indifferent to its common consequence. Under the assumption of segregation, such gambles can be expressed as the joint receipt of the common consequence and what we call `an element of chance', namely, the same gamble with the common consequence replaced by the status quo. Generalizing, any gamble is indifferent to the joint receipt of its element of chance and a certain consequence, which is called the `kernel equivalent' of the gamble. Under idempotence, the kernel equivalent equals the certainty equivalent. Conditions are reported (Theorem 4) that are sufficient for the kernel equivalents to have the kind of utility representation first discussed by Luce and Fishburn (1991), including being idempotent. This utility representation of the kernel equivalents together with the derived form of utility over joint receipts yields a utility representation of the original structure. Possible forms for the utility of an element of chance are developed. [ABSTRACT FROM AUTHOR]

We define a new way of combining operators on a partially ordered set: the one-parameter toggle. Under some conditions, iteration of toggles and join operations applied to algebraic openings leads to a new family of idempotent operators having an order-theoretic property that we call condensation. This methodology can be used to design algorithms for the description and approximation of spatial shapes. [ABSTRACT FROM AUTHOR]

In this note, we first consider a ternary matrix group related to the von Neumann regular semigroups and to the Artin braid group (in an algebraic way). The product of a special kind of ternary matrices (idempotent and of finite order) reproduces the regular semigroups and braid groups with their binary multiplication of components. We then generalize the construction to the higher arity case, which allows us to obtain some higher degree versions (in our sense) of the regular semigroups and braid groups. The latter are connected with the generalized polyadic braid equation and R-matrix introduced by the author, which differ from any version of the well-known tetrahedron equation and higher-dimensional analogs of the Yang-Baxter equation, n-simplex equations. The higher degree (in our sense) Coxeter group and symmetry groups are then defined, and it is shown that these are connected only in the non-higher case. [ABSTRACT FROM AUTHOR]

In this paper, we present a comprehensive analysis of self-dual and m--idempotent operators. We refer to an operator as m-idempotent if it converges after m iterations. We focus on an important special case of the general theory of lattice morphology: spatially variant morphology, which captures the geometrical interpretation of spatially variant structuring elements. We demonstrate that every increasing self-dual morphological operator can be viewed as a morphological center. Necessary and sufficient conditions for the idempotence of morphological operators are characterized in terms of their kernel representation. We further extend our results to the representation of the kernel of m-idempotent morphological operators. We then rely on the conditions on the kernel representation derived and establish methods for the construction of m--idempotent and self-dual morphological operators. Finally, we illustrate the importance of the self-duality and m-idempotence properties by an application to speckle noise removal in radar images. [ABSTRACT FROM AUTHOR]