On the poset of computation rules for nonassociative calculus
Grabisch, Michel; Couceiro, Miguel (2013), On the poset of computation rules for nonassociative calculus, Order, 30, 1, p. 269288. http://dx.doi.org/10.1007/s110830119243z
Type
Article accepté pour publication ou publiéExternal document link
http://arxiv.org/abs/1105.4174Date
2013Journal name
OrderVolume
30Number
1Publisher
Springer
Pages
269288
Publication identifier
Metadata
Show full item recordAbstract (EN)
The symmetric maximum, denoted by v, is an extension of the usual max operation so that 0 is the neutral element, and x is the symmetric (or inverse) of x, i.e., x v(x)=0. However, such an extension does not preserve the associativity of max. This fact asks for systematic ways of parenthesing (or bracketing) terms of a sequence (with more than two arguments) when using such an extended maximum. We refer to such systematic (predefined) ways of parenthesing as computation rules. As it turns out there are infinitely many computation rules each of which corresponding to a systematic way of bracketing arguments of sequences. Essentially, computation rules reduce to deleting terms of sequences based on the condition x v(x)=0. This observation gives raise to a quasiorder on the set of such computation rules: say that rule 1 is below rule 2 if for all sequences of numbers, rule 1 deletes more terms in the sequence than rule 2. In this paper we present a study of this quasiordering of computation rules. In particular, we show that the induced poset of all equivalence classes of computation rules is uncountably infinite, has infinitely many maximal elements, has infinitely many atoms, and it embeds the powerset of natural numbers ordered by inclusion.Subjects / Keywords
Partially ordered set; Computation rule; Nonassociative algebra; Symmetric maximumRelated items
Showing items related by title and author.

Brabant, Quentin; Couceiro, Miguel; Dubois, Didier; Prade, Henri; Rico, Agnès (2018) Communication / Conférence

Lehtonen, Erkko; Couceiro, Miguel; Couceiro, Miguel (2008) Communication / Conférence

Labreuche, Christophe; Grabisch, Michel; Mayag, Brice (2011) Communication / Conférence

Mayag, Brice; Grabisch, Michel; Labreuche, Christophe (2009) Communication / Conférence

Mayag, Brice; Grabisch, Michel; Labreuche, Christophe (2009) Article accepté pour publication ou publié